Python - 算法分析

算法的效率可以在两个不同的阶段进行分析，即实施前和实施后。 他们是以下这些 −

• 先验分析 − 这是一个算法的理论分析。 算法的效率是通过假设所有其他因素（例如处理器速度）保持不变并且对实现没有影响来衡量的。

• 事后分析 − 这是一个算法的实证分析。 所选算法是使用编程语言实现的。 然后在目标计算机上执行。 在此分析中，收集实际统计数据，如运行时间和所需空间。

算法复杂度

假设X是一个算法，n是输入数据的大小，算法X使用的时间和空间是决定X效率的两个主要因素。

• 时间因素 − 时间是通过统计排序算法中的比较等关键操作的次数来衡量的。

• 空间因素 − 空间是通过计算算法所需的最大内存空间来衡量的。

算法的复杂性 f(n) 以 n 作为输入数据的大小给出了算法所需的运行时间和/或存储空间。

空间复杂度

算法的空间复杂度表示算法在其生命周期中所需的内存空间量。 算法所需的空间等于以下两个部分的总和 −

• 一个固定的部分，它是存储某些数据和变量所需的空间，与问题的大小无关。 例如，使用的简单变量和常量、程序大小等。

• 可变部分是变量所需的空间，其大小取决于问题的大小。 例如动态内存分配、递归栈空间等。

任意算法P的空间复杂度S(P)为 S(P) = C + SP(I)，其中C为固定部分，S(I)为算法的可变部分，取决于实例特征I。下面是一个简单的例子，试图解释这个概念 −

算法: SUM(A, B)

步骤 1 − START

步骤 2 − C ← A + B + 10

步骤 3 − Stop

这里我们有三个变量 A、B 和 C 以及一个常量。 因此 S(P) = 1 + 3。 现在，空间取决于给定变量和常量类型的数据类型，并且会相应地成倍增加。

时间复杂度

算法的时间复杂度表示算法运行到完成所需的时间量。 时间要求可以定义为数值函数 T(n)，其中 T(n) 可以测量为步骤数，前提是每个步骤消耗恒定时间。

例如，两个 n 位整数相加需要 n 步。 因此，总计算时间为 T(n) = c ∗ n，其中 c 是添加两位所花费的时间。 在这里，我们观察到 T(n) 随着输入大小的增加而线性增长。