python 算法分析

算法分析

算法的效率可以在执行之前和执行之后的两个不同阶段进行分析。他们是以下 -

• 先验分析 - 这是一种算法的理论分析。 算法的效率是通过假设所有其他因素（例如处理器速度）是恒定的并且对实现没有影响来衡量的。

• 后验分析 - 这是对算法的经验分析。 所选择的算法使用编程语言来实现。然后在目标计算机上执行。在此分析中，收集实际的统计数据，如运行时间和所需空间。

算法的复杂性

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

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

• 空间因子 - 空间通过计算算法所需的最大存储空间来测量。

所述算法的复杂性 f（n） 给出的运行时间和/或在以下方面由该算法所需的存储空间 Ñ 作为输入数据的大小。

空间复杂性

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

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

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

任何算法p的空间复杂度s（p）是s（p）= c + sp（i），其中c是固定部分，s（i）是算法的可变部分，取决于实例特征i.是一个简单的例子，试图解释这个概念 -

algorithm: sum(a, b)
step 1 -  start
step 2 -  c ← a + b + 10
step 3 -  stop

这里我们有三个变量a，b和c以及一个常量。因此s（p）= 1 + 3.现在，空间取决于给定变量和常量类型的数据类型，并且它将相应地相乘。

时间复杂性

算法的时间复杂度表示算法运行完成所需的时间量。时间要求可以定义为一个数值函数t（n），其中t（n）可以测量为步数，只要每步消耗的时间恒定。

例如，添加两个n位整数需要 n个 步骤。因此，总计算时间是t（n）= c * n，其中c是加两位所用的时间。在这里，我们观察到t（n）随着输入尺寸的增加而线性增长。