Python - 算法分析

• 

  简述

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

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

  算法复杂度

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

  • Time Factor− 时间是通过计算排序算法中的比较等关键操作的数量来衡量的。
  • Space Factor− 空间是通过计算算法所需的最大内存空间来衡量的。

  算法的复杂度f(n)给出算法所需的运行时间和/或存储空间n作为输入数据的大小。
• 

  空间复杂度

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

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

  任何算法 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。现在，空间取决于给定变量和常量类型的数据类型，并将相应地相乘。
• 

  时间复杂度

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

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