当算法问题的规模很小的时候，基本上在任何一台机器上都会以很快的速度计算出来，只有在问题规模较大的时候分析算法的效率才显得有意义。因此我们要研究算法的渐进效率，也就是关心问题的输入规模趋向无穷大时，算法的运行时间是如何增长的。

本文将以插入排序为例，简要分析其运行时间。这种分析将引入一种关注时间如何随着输入规模增加而增加的记号。在此基础上，再给出几种标准方法来简化算法的渐进分析。

1. 插入排序

1.1 算法描述

插入排序的工作方式就像你排序手中的扑克牌一样（假设从左到右是从小到大），一开始手中没有牌，每次拿到一张新的牌都要从右到左与每张牌比较，并将其插入到合适的位置（比它大的牌也顺势后移）。以下是Python代码：

def insertionSort(data):
    # 初始化结果为第一个数
    result = [data[0]]
    # 从第二个数开始，从后往前找应该插入的位置
    for key in data[1:]:
        index = len(result) - 1
        while index >= 0 and result[index] > key:
            index -= 1
        else:
            result.insert(index + 1, key)
    return result

注：上述代码使用了Python list的insert方法在特定位置插入一个数（其他数字顺势往后移），如果是用C/C++之类普通的数组可能需要自己手动来后移其他数字。

1.2 算法分析

即使对给定规模的输入，一个算法的运行时间也可能依赖于该规模下不同的输入。例如在最佳情况下，输入的数组本身就是有序的，因此不需要里层的while循环来查找插入位置，只要直接插入即可，运行时间为线性函数$an + b$；在最坏情况下，输入的数组是反序的，里层while循环必须将每个元素key与整个已排序的子数组进行比较，运行时间是二次函数$a{n^2} + bn + c$。

在算法的性能分析中，我们往往关注算法在最坏情况的运行时间，这是因为：

• 算法的最坏情况运行时间给出了任何输入的运行时间的一个上界。知道这个界限，就能确保该算法运行肯定不会需要更长的时间。
• 对某些算法，最坏情况经常出现。例如检索数据库特定信息时，该信息不存在的情况（即最坏情况）是经常出现的。
• “平均情况”往往与最坏情况大致一样差。例如插入排序寻找插入位置时，平均来说插入的位置大致处于已排序数组的“中间”，即检查一半的元素。这种“平均情况”最终得出的运行时间也是输入规模的二次函数。

我们真正感兴趣的是算法运行时间的增长率。当n很大时，低阶项相对来说不太重要，常量因子也不如增长率重要，所以我们只考虑公式中阶数最大的项，上述公式即是${n^2}$。我们记插入排序最坏运行时间为$T(n) = \Theta ({n^2})$。下一节将讲解这种特殊符号的真正含义。

2. 渐近记号

上面提到插入排序最坏的运行时间为$T(n) = \Theta ({n^2})$，一般我们使用渐近记号来描述算法的运行时间。最常用的渐近记号有$\Theta $记号，大O记号和$\Omega $记号。

• $T(n) = \Theta (f(n))$：当且仅当存在正常数${c_1},{c_2},{n_0}$，使得对所有$n \ge {n_0}$，有$0 \le {c_1}f(n) \le T(n) \le {c_2}f(n)$
• $T(n) = O(f(n))$：当且仅当存在正常数$c,{n_0}$，使得对所有$n \ge {n_0}$，有$0 \le T(n) \le cf(n)$
• $T(n) = \Theta (f(n))$：当且仅当存在正常数$c,{n_0}$，使得对所有$n \ge {n_0}$，有$0 \le cf(n) \le T(n)$

由上述定义可见，其实三种符号的定义非常相像，其中$\Theta $记号渐近地给出一个函数的上界和下界，而大O记号给出的是上界，$\Omega $记号给出的是下界。因此接下来的讨论均以“较为严格”的$\Theta $记号为例。下图给出这三种记号的一个直观表示。

注意，由于$\Theta (f(n))$是一个集合，所以$T(n) = \Theta (f(n))$其实等价于$T(n) \in \Theta (f(n))$。$\Theta $记号的一种非形式化的概念，相当于扔掉低阶项并忽略最高阶项前的系数。

例1：证明${1 \over 2}{n^2} - 3n = \Theta ({n^2})$

证明：要确定${c_1},{c_2},{n_0}$，使得对所有$n \ge {n_0}$，有${c_1}{n^2} \le {1 \over 2}{n^2} - 3n \le {c_2}{n^2}$成立
即${c_1} \le {1 \over 2} - {3 \over n} \le {c_2}$。
通过选择${c_2} \ge {1 \over 2}$，可以使右边不等式对任何$n \ge 1$成立
通过选择${c_1} \le {1 \over {14}}$，可以使左边不等式对任何$n \ge 7$成立。QED

例2：证明$6{n^3} \ne \Theta ({n^2})$

证明：采用反证法。假设存在${c_2},{n_0}$，使得对所有$n \ge {n_0}$，有$6{n^3} \le {c_2}{n^2}$。用${n^2}$除该式，得$n \le {c_2}$，因为${c_2}$是常量，所以对任意大的$n$，该不等式不可能成立。QED

例3：解释$2{n^2} + 3n + 1 = 2{n^2} + \Theta ({n^2}) = \Theta ({n^2})$

第一个等式表明存在某个函数$f(n) \in \Theta ({n^2})$，使得对所有的$n$，有$2{n^2} + 3n + 1 = 2{n^2} + f(n)$。第二个等式表明对任意函数$g(n) \in \Theta ({n^2})$，存在某个函数$h(n) \in \Theta ({n^2})$，使得对所有的$n$，有$2{n^2} + g(n) = h(n)$。

参考文献：机械工业出版社《算法导论（第3版）》2.1节，2.2节，第3章

上一篇：算法学习笔记：分治法

下一篇：【演示】前端自动化工作流简介