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