算法分析

算法是平台无关的，也即一个算法可以在任意计算机、任意操作系统上、用任意编程语言实现。因此，算法性能的相对好坏，不能仅仅通过基于运行记录的经验来判断。

举例：一个程序在大小为 n 的有序数组中搜索元素。假设该程序在一台先进的电脑 A 上用线性搜索实现，在一台老旧的电脑 B 上用二分搜索实现。性能测试的结果可能会如下：

通过这些数据，很容易得出结论说计算机 A 运行的算法比计算机 B 的算法要高效得多。但假如输入的数组长度显著增加的话，很容易发现这个结论的错误。 以下是另一组数据：

计算机 A 运行的线性搜索算法具有线性时间。它的运行时间直接与输入规模成正比。输入大小若加倍，运行时间同样加倍。而计算机 B 运行的二分搜索算法具有对数时间。输入大小若加倍，运行时间仅仅增加一个常量，在此例中是 25,000 纳秒。即使计算机 A 明显性能更强，在输入不断增加的情况下，计算机 B 的运行时间终究也会比计算机 A 更短，因为它运行的算法的增长率小得多。

非正式地，如果一个关于 ${\displaystyle n}$ 的函数 ${\displaystyle f(n)}$，乘以一个系数以后，能够为某个算法在输入数据大小 ${\displaystyle n}$ 足够大的情况下的运行时间提供一个上界，那么称此算法按该函数的阶增长。一个等价的描述是，当输入大小 ${\displaystyle n}$ 大于某个 ${\displaystyle n_{0}}$ 时，存在某个常数 ${\displaystyle c}$，使得算法的运行时间总小于 ${\displaystyle c\times f(n)}$。常用大O符号对此进行描述。比如，插入排序的运行时间随数据大小二次增长，那么插入排序具有 ${\displaystyle O(n^{2})}$ 的时间复杂度。大O符号通常用于表示某个算法在最差情况下的运行时间，但也可以用来表述平均情况的运行时间。比如，快速排序的最坏运行时间是 ${\displaystyle O(n^{2})}$，但是平均运行时间则是 ${\displaystyle O(n\log n)}$。[7]

分析一个算法的最坏运行时间复杂度时，人们常常作出一些简化问题的假设，并分析该算法的结构。以下是一个例子：

1    从输入值中获取一个正数
2    if n > 10
3        print "耗时可能较长，请稍候……"
4    for i = 1 to n
5        for j = 1 to i
6            print i * j
7    print "完成！"

一台给定的电脑执行每一条指令的时间是确定[8]的，并可以用 DTIME 描述。 假设第 1 步操作需时 T₁，第 2 步操作需时 T₂，如此类推。

步骤 1、2、7 只会运行一次。应当假设在最坏情况下，步骤 3 也会运行。步骤 1 至 3 和步骤 7 的总运行时间是：

${\displaystyle T_{1}+T_{2}+T_{3}+T_{7}}$

步骤 4、5、6 中的循环更为复杂。步骤 4 中的最外层循环会执行 (n + 1) 次（需要一次执行来结束 for 循环，因此是 (n + 1) 次而非 n 次），因此会消耗 T₄ × (n + 1) 单位时间。内层循环则由 i 的值控制，它会从 1 迭代到 n。 第一次执行外层循环时，j 从 1 迭代到 1，因此内层循环也执行一次，总共耗时 T₆ 时间。以及内层循环的判断语句消耗 3T₅ 时间。

所以，内层循环的总共耗时可以用一个等差级数表示：

${\displaystyle T_{6}+2T_{6}+3T_{6}+\cdots +(n-1)T_{6}+nT_{6}}$

上式可被因式分解[9]为：

${\displaystyle T_{6}\left[1+2+3+\cdots +(n-1)+n\right]=T_{6}\left[{\frac {1}{2}}(n^{2}+n)\right]}$

类似地，可以分析内层循环的判断语句：

${\displaystyle 2T_{5}+3T_{5}+4T_{5}+\cdots +(n-1)T_{5}+nT_{5}+(n+1)T_{5}}$

${\displaystyle =T_{5}+2T_{5}+3T_{5}+4T_{5}+\cdots +(n-1)T_{5}+nT_{5}+(n+1)T_{5}-T_{5}}$

上式可被分解为：

${\displaystyle T_{5}\left[1+2+3+\cdots +(n-1)+n+(n+1)\right]-T_{5}}$

${\displaystyle =\left[{\frac {1}{2}}(n^{2}+n)\right]T_{5}+(n+1)T_{5}-T_{5}}$

${\displaystyle =T_{5}\left[{\frac {1}{2}}(n^{2}+n)\right]+nT_{5}}$

${\displaystyle =\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}}$

因此该算法的总运行时间为：

${\displaystyle f(n)=T_{1}+T_{2}+T_{3}+T_{7}+(n+1)T_{4}+\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}}$

改写一下：

${\displaystyle f(n)=\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}}$

通常情况下，一个函数的最高次项对它的增长率起到主导作用。在此例里，n² 是最高次项，所以有结论 ${\displaystyle f(n)=O(n^{2})}$。

严格证明如下：证明 ${\displaystyle \left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}}$

${\displaystyle \left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}}$

${\displaystyle \leq (n^{2}+n)T_{6}+(n^{2}+3n)T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\ (n\geq 0)}$

令 k 为一个常数，其大于从 T₁ 到 T₇ 所有的数。

${\displaystyle T_{6}(n^{2}+n)+T_{5}(n^{2}+3n)+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq k(n^{2}+n)+k(n^{2}+3n)+kn+5k}$

${\displaystyle =2kn^{2}+5kn+5k\leq 2kn^{2}+5kn^{2}+5kn^{2}\,(n\geq 1)=12kn^{2}}$

因此有

${\displaystyle \left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}}$，其中 ${\displaystyle c=12k,n_{0}=1}$

还可以假定所有步骤全部消耗相同的时间，它的值比 T₁ 到 T₇ 中任意一个都大。这样的话，这个算法的运行时间就可以这样来分析：[10]

${\displaystyle 4+\sum _{i=1}^{n}i\leq 4+\sum _{i=1}^{n}n=4+n^{2}\leq 5n^{2}\,(n\geq 1)=O(n^{2}).}$