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)随着输入大小的增加而线性增长。