随着计算机处理数据量的增大，程序运行时消耗的时间与内存空间也逐步增加。对于同一个问题，不同的算法解决方案所耗费的代价不尽相同，对算法的性能进行合理、准确的分析可以为算法的选择、改进提供可靠的依据。

算法分析方法

算法分析的基础是科学的研究方法，即：使用数学分析为算法成本建立简洁的模型并使用实验数据验证这些模型。其基本步骤如下：

  • 细致的观察真实世界的特点，通常还要有精确的测量；
  • 根据观察结果提出加收模型；
  • 根据模型预测未来的事件；
  • 继续观察并核实预测的准确性；
  • 如此反复直到确认预测和观察一致。

科学的研究方法有两个重要原则：

  1. 所设计的实验必须是可重现的；
  2. 所有的假设也必须是可证伪的。

数学模型

一个程序的运行总时间主要和两点有关：

  • 执行每条语句的耗时
  • 执行每条语句的次数

其中前者取决于计算机、程序编译器及操作系统等因素；后者取决于程序本身及输入的数据。

基本操作耗时

下表为Java中一些基本操作耗时

操作 举例 耗时（纳秒）*
整数加法 a + b 2.1
整数乘法 a * b 2.4
整数除法 a / b 5.4
浮点数加法 a + b 4.6
浮点数乘法 a * b 4.2
浮点数除法 a / b 13.5
正弦 Math.sin(theta) 91.3
反正切 Math.atan2(y, x) 129.0
… … …

*不同编译器、计算机及操作系统结果可能有差异

可以看出，不同的基本操作一般耗时不同。一般在进行算法分析时会假定每个不同指令所需的执行时间是固定不变的。需要注意的是，在指令执行中，非基本操作（Non-primitive operation）的耗时一般要比基本操作耗时多。

执行次数统计

对于以下代码片段，当输入大小为N时，其每个操作的执行次数是多少： 

1
2
3
4
5
6
int count = 0;
for (int i = 0; i < N; i++) {
    if (a[i] == 0) {
        count++;
    }
}

操作 次数
变量定义 2
赋值操作 2
小于比较 N + 1
等于比较 N
数组访问 N
自增操作 N ~ 2N

观察上述代码片段可以发现，执行最频繁的指令决定了程序执行的总时间，具体来说就是for循环内的if语句块。一般将这些指令称为程序的内循环。

近似

根据程序运算时间的计算方法，假设以上代码块中各项操作的耗时如下：

操作 耗时 次数
变量定义 a 2
赋值操作 b 2
小于比较 c N + 1
等于比较 d N
数组访问 e N
自增操作 f N + x *

*假设输入的N个数据中有x个为0。

则操作的总耗时为： (c + d + e + f)N + (2a + 2b + c + xf)

这样的表达较为复杂冗长。一般在这种表达式中，首相（幂数最高项）之后的项之和相对较小。那么操作的总耗时可以近似表达为： ~ (c + d + e + f)N

由于我们假设每个操作的耗时是固定不变的，那么在分析比较算法时可以省略这些相同的参数，简化为： ~ N

同时更应该关注的是耗时随输入增长的数量级。对于上述例子来说就是N即，该代码片段的运行耗时随输入的增长是线性级别的。

一般方法

对于大多数程序，得到其运行时间的数学模型所需的步骤如下：

  • 确定输入模型，定义问题的规模
  • 识别内循环
  • 根据内循环中的操作确定成本模型
  • 对于给定的输入，判断这些操作的执行频率

如果一个程序含有多个方法，分别讨论它们。

增长数量级的分类

算法运行成本增长的数量级一般都是问题规模N的若干函数之一，下表给出了常见的增长数量级：

描述 增长数量级 说明 举例
常数级别 1 普通语句 将两个数相加
对数级别 logN 二分策略 二分查找
线性级别 N 循环 找出最大数
线性对数级别 NlogN 分治 归并排序
平方级别 N^2 双层循环 检查所有元素对
立方级别 N^3 三层循环 检查所有三元组
指数级别 2^N 穷举查找 检查所有子集

算法分析

算法分析的分类

算法的性能分析中，随着输入的不同可能的性能表现也不同。

以二分查找为例：输入的数组顺序会影响查找的效率，在最好的情况下，第一次查找就可以找到所需的元素，此时的算法性能为~1即常数级别，但是在最坏的情况下，还是需要~lgN次查找才能找到所需元素。

对应的有三种不同情况下的算法性能：

  • 最好情况：算法开销的下限
    • “最有利”的输入
    • 为所有的输入提供了一个最小开销的目标
  • 最差情况：算法性能的上限
    • “最不利”的输入
    • 为所有输入提供了一个最大开销的保证
  • 平均情况：随机输入下的期望开销
    • 需要“随机的输入”
    • 提供了算法的预期表现

上下限

算法分析可以确定问题的“复杂程度”，同时为开发“最理想”的算法提供依据。在算法分析中，通过分析不变因素下的算法性能可以减少算法分析的细节；同时，关注最差情况下的算法性能可以消除输入数据的差异对算法性能的影响。

通过算法分析能够获得算法复杂度的上限与下限：

  • 理论上限：算法性能的最低保证，实际使用中算法的复杂度不高于理论上限。
  • 理论下限：算法性能的最好情况，实际使用中算法复杂度不可能低于其理论下限。

当一个算法的理论上限与理论下限相同时，称其为最佳算法（Optimal algorithm），该算法的性能不受输入情况的影响，在任何情况下都能保证运行时间在理论范围内。

算法分析中常用符号

下表列出了算法分析中常用的表示算法复杂度的符号及其意义：

符号 代表意义 示例 可表示表达式 用途
波浪号 算法复杂度首相 ~10N^2 10N^2 + 22NlogN 近似的数学模型
大写Theta 算法复杂度增长情况 Θ(N^2) 5N^2 + 22NlogN 算法分类
大写O 可能的最大算法复杂度（为Θ(N^2)或更小） O(N^2) 5N^2 + 22NlogN 或 3N 算法复杂度的理论上限
大写Omega 可能的最小算法复杂度（为Θ(N^2)或更大） Ω(N^2) 5N^2 或 N^3 + 22Nlog N + 3N 算法复杂度的理论下限