Python Data Structure 简明教程

Python - Algorithm Analysis

算法的效率可以在两个不同的阶段进行分析，在实现之前和实现之后。它们如下所示 −

  1. A Priori Analysis − 这是对算法的理论分析。算法的效率通过假设所有其他因素，例如处理器速度，都是常量并且对实现没有影响来衡量的。

  2. A Posterior Analysis − 这是对算法的经验分析。选定的算法使用编程语言实现。然后在目标计算机上执行此操作。在此分析中，收集实际统计信息，如运行时间和所需的存储空间。

Algorithm Complexity

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

  1. Time Factor − 时间通过计算诸如排序算法中的比较之类的关键操作的数量来衡量。

  2. Space Factor − 空间通过计算算法所需的最大的内存空间来衡量。

算法 f(n) 的复杂度根据输入数据的规模 n 给出了算法的运行时间和/或存储空间要求。

Space Complexity

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

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

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

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

Algorithm: SUM(A, B)

步骤 1 − 开始

步骤 2 − C ← A + B + 10

步骤 3 − 停止

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

Time Complexity

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

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