Python数据结构 算法分析

一个算法的效率可以在两个不同的阶段进行分析，即实现前和实现后。它们是以下几点

• 先验分析 – 这是一个算法的理论分析。假设所有其他因素，例如处理器速度，都是恒定的，并且对实现没有影响，那么就可以衡量算法的效率。

• 后验分析– 这是对一种算法的经验分析。选定的算法是用编程语言实现的。然后在目标计算机机器上执行。在这种分析中，实际的统计数据，如运行时间和所需空间，都被收集起来。

算法复杂度

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

• 时间因素– 时间是通过计算关键操作的数量来衡量的，如排序算法中的比较。

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

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

空间复杂度

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

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

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

任何算法P的空间复杂度S(P)是S(P)=C+SP(I)，其中C是固定部分，S(I)是算法的可变部分，这取决于实例特征I。

算法。SUM(A, B)

第1步 – 开始

第2步 – C ← A + B + 10

第3步 – 停止

这里我们有三个变量A、B、C和一个常数。因此，S(P) = 1 + 3。现在，空间取决于给定变量的数据类型和常数类型，它将被相应地乘以。

时间复杂度

一个算法的时间复杂度代表了该算法运行到完成所需的时间量。时间要求可以定义为一个数字函数T(n)，其中T(n)可以用步骤数来衡量，只要每一步消耗的时间不变。

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