Python算法设计：复杂度分析

算法效率可以分执行前和执行后两个不同阶段进行分析。它们如下 -

• 先验分析 - 这是算法的理论分析。算法的效率是通过假设所有其他因素（例如处理器速度）恒定并且对实现没有影响来衡量的。
• 后验分析 - 这是算法的实证分析。所选算法是使用编程语言实现的。然后在目标计算机上执行。在此分析中，收集实际统计数据，例如驾驶时间和所需空间。

算法复杂度

假设影响X的效率主要有两个因素。

• 时间因素 - 时间是通过计算关键操作的数量来衡量的，例如排序算法中的比较。
• 空间因子 - 通过计算算法所需的最大存储空间来衡量空间。

算法f(n)的复杂性是通过算法n所需的运行时间和/或存储空间来衡量的，即数据的大小。

空间复杂度

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

• 固定部分是存储某些数据和变量所需的空间，无论问题的大小如何。例如使用的简单变量和常量、程序大小等。
• 变量部分是变量所需的空间，其大小取决于问题的大小。例如。动态内存分配、递归堆栈空间等。

任意算法P的空间复杂度S(P)为+ SP(I)，其中C 是固定部分，S(I) 是算法的可变部分❝，取决于实例特征 I♺❀ ，下面是一个尝试解释的简单示例概念 -

Algorithm: SUM(A, B)
Step 1 -  START
Step 2 -  C ← A + B + 10
Step 3 -  Stop

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

时间复杂度

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

例如，两个n位整数相加需要n步。因此，总计算时间为 T(n)= c * n，其中 c 是两个数字相加所需的时间。此处观察到 T(n) 随着输入大小的增加而线性增长。