Skip to content

算法和算法评价

算法的时间复杂度分析 | Linux C 编程一站式学习

算法效率评估 | Hello 算法

时间复杂度 | Hello 算法

同一问题往往有多种算法. 要比较它们的好坏, 408 主要看两件事: 能不能正确把问题解完, 以及 时间和额外空间随规模怎么长. 后者就是复杂度分析.

算法

算法（algorithm）是对特定问题求解步骤的一种描述, 是指令的有限序列, 每条指令表示一个或多个操作. 「程序 = 数据结构 + 算法」指的就是先把数据组织好, 再给出在这些数据上的操作步骤.

算法与程序

算法是抽象的解题方法, 程序是算法在某种语言里的实现.

关键差别在有穷性: 算法必须在有限步后停下来; 程序可以写成死循环 (操作系统、服务进程就是故意不终止的). 同一算法也可以对应多种程序 (C / Python / 伪代码).

算法的五个基本特性

  1. 有穷性: 执行有穷步后结束, 且每一步都能在有穷时间内完成

  2. 确定性: 每条指令含义明确, 相同输入只能得到相同输出

  3. 可行性: 每步都能用已经实现的基本运算做有限次

  4. 输入: 零个或多个, 取自某个对象集合

  5. 输出: 一个或多个, 与输入有确定关系

Note

「零个输入」是合法的, 例如打印固定常数的算法. 「至少一个输出」是必须的, 否则看不出算法做了什么.

优秀算法的特征

特性只保证「这是算法」, 优秀算法还追求:

  • 正确性: 对合法输入给出符合规格的结果

  • 可读性: 人能看懂, 方便验证和修改

  • 健壮性: 非法输入时能报错或妥善处理, 而不是给出莫名其妙的结果

  • 高效率、低存储: 时间复杂度低, 空间复杂度低

正确性可以用循环不变式或递归的 Base Case + 递推来证明; 效率则用下面的渐近分析来衡量.

复杂度分析的本质

事后在机器上跑一遍, 结果依赖 CPU、语言、编译器优化、缓存, 不同的机器/平台结果不尽相同.

复杂度分析做的是事前估计: 不关心某一条指令是 1 ns 还是 3 ns, 只关心当问题规模 \(n\) 变大时, 时间和空间涨得有多快.

因此可以把每条语句的耗时看成常数 (上界一定是常数; 受缓存影响未必每次都相同, 粗略估计够用), 把「计时」简化成「数基本操作执行了多少次」.

时间复杂度

设问题规模为 \(n\) (排序里是元素个数, 图里常指 \(|V|\) 或 \(|E|\)). 算法中某个基本操作的执行次数是 \(n\) 的函数 \(f(n)\), 则时间开销记为 \(T(n)\). 渐近时间复杂度取 \(f(n)\) 的增长量级, 408中通常写成

\[ T(n) = O(f(n)) \]

\(n\) 足够大以后, \(T(n)\) 的增长不超过 \(f(n)\) 的常数倍.

时间复杂度的计算步骤

  1. 找基本操作, 一般是最内层循环体里执行次数最多的那句 (比较、移动、赋值)

  2. 写出它关于 \(n\) 的频度 \(f(n)\)

  3. 只留最高次项, 丢掉系数和低次项, 得到 \(O(\cdot)\)

推导时常用两条规则:

  • 加法: 依次执行 \(O(f)\) 和 \(O(g)\), 总复杂度 \(O(\max(f, g))\)

  • 乘法: 嵌套时频度相乘, \(O(f) \cdot O(g) = O(fg)\)

顺序执行的代码只贡献常数, 可以忽略; 嵌套循环每深一层, 往往就多乘一个 \(n\).

演算示例

for (i = 1; i <= n; i++)
    for (j = 1; j <= i; j++)
        x++;

内层对每个 \(i\) 跑 \(i\) 次, 总次数 \(\sum_{i=1}^{n} i = n(n+1)/2 = O(n^2)\).

for (i = 1; i <= n; i *= 2)
    x++;

\(i\) 每次翻倍, 循环约 \(\lfloor \log_2 n \rfloor + 1\) 次, \(O(\log n)\). 对数就是这样从「每次把规模砍半 / 翻倍」里冒出来的, 不是从加减乘里凭空出现的. 折半查找、归并排序的 \(\log n\) 同源.

最好、最坏、平均时间复杂度

同一算法, \(T(n)\) 还可能随输入内容变, 不只随 \(n\) 变. 以直接插入排序为例 (输入长度记为 \(n\)):

void insertion_sort(int a[], int n) {
    int i, j, key;
    for (j = 1; j < n; j++) {          /* 外层 n-1 次 */
        key = a[j];                   /* c1 */
        i = j - 1;                    /* c2 */
        while (i >= 0 && a[i] > key) {
            a[i + 1] = a[i];          /* c3 */
            i--;                      /* c4 */
        }
        a[i + 1] = key;               /* c5 */
    }
}

外层固定 \(n-1\) 次. 设内层 while 平均每次跑 \(m\) 圈, 总时间大约是

\[ (n-1)\bigl(c_1 + c_2 + c_5 + m(c_3 + c_4)\bigr) \]

\(m\) 不是常数, 也不由 \(n\) 单独决定, 而取决于数组长什么样:

  • 最好 (已正序): while 一次都不进, \(m = 0\), 时间是 \(an+b\), 线性, \(\Theta(n)\)

  • 最坏 (逆序): 每插入一个 key 都要挪开左侧全部元素, \(m\) 对 \(j=1,\ldots,n-1\) 分别取 \(1,2,\ldots,n-1\), 总和 \(n(n-1)/2\), 时间是 \(an^2+bn+c\), 二次, \(\Theta(n^2)\)

  • 平均 (随机): 左侧大约一半比 key 大, \(m \approx j/2\), 总和仍是 \(\Theta(n^2)\)

比较次数、移动次数的精确求和见插入排序的算法分析.

为什么更关心最坏时间复杂度

  1. 最坏情况是执行时间的上界, 任意输入都不会更差, 方便比较

  2. 有些问题里最坏最常见, 例如查找失败要把表扫完 (顺序查找失败)

  3. 很多算法的平均和最坏属于同一量级, 插入排序就是: 平均、最坏都是 \(n\) 的二次函数

最好情况往往要输入满足很苛刻的条件 (已经排好序), 单独拿来当「这个算法很快」容易误导.

渐进记号

多项式里, \(n\) 的最高次决定量级: 比较 \(100n+1\) 和 \(n^2+1\), 当 \(n>100\) 后后者远大. 系数、低次项、常数在 \(n \to \infty\) 时都可以丢掉. 于是用集合来写「同一量级」.

西塔记号

\(\Theta(g(n))\) 表示和 \(g(n)\) 同一量级的一类函数. 若能找到正常数 \(c_1\)、\(c_2\)、\(n_0\), 使得 \(n \geqslant n_0\) 时

\[ c_1 g(n) \leqslant f(n) \leqslant c_2 g(n) \]

就说 \(f(n) = \Theta(g(n))\) (更严谨是 \(f \in \Theta(g)\)). \(\Theta\) 的含义接近「等于」: 上下都被 \(g\) 卡住, 是渐近紧确界.

\(\tfrac{1}{2}n^2 - 3n = \Theta(n^2)\)

要证存在 \(c_1,c_2,n_0\) 使 \(n \geqslant n_0\) 时 \(c_1 n^2 \leqslant \tfrac{1}{2}n^2 - 3n \leqslant c_2 n^2\). 两边除以 \(n^2\):

\[ c_1 \leqslant \tfrac{1}{2} - \tfrac{3}{n} \leqslant c_2 \]

对任意 \(n>0\), 该式都 \(< 1/2\), 取 \(c_2 = 1/2\). \(n=7\) 时 \(\tfrac{1}{2}-\tfrac{3}{7}=\tfrac{1}{14}\), 之后都更大, 故可取 \(n_0=7\), \(c_1=1/14\).

任意 \(an^2+bn+c\) 在 \(n\) 足够大时都能这样夹进 \(c_1 n^2\) 与 \(c_2 n^2\) 之间: \(bn+c\) 相对 \(n^2\) 可忽略, \(a\) 靠选取 \(c_1,c_2\) 补偿.

渐进上界和渐进下界

  • 大 \(O\) (渐进上界, 类似 \(\leqslant\)): 存在 \(c,n_0\), 使 \(n \geqslant n_0\) 时 \(0 \leqslant f(n) \leqslant c\,g(n)\)

  • \(\Omega\) (渐进下界, 类似 \(\geqslant\)): 存在 \(c,n_0\), 使 \(n \geqslant n_0\) 时 \(0 \leqslant c\,g(n) \leqslant f(n)\)

  • \(f = \Theta(g)\) 当且仅当 \(f = O(g)\) 且 \(f = \Omega(g)\).

408的写法

考研几乎只写 \(O\), 不强调 \(\Theta\). 看到「时间复杂度 \(O(n^2)\)」默认指最坏上界. 说「插入排序是 \(O(n^2)\)」正确; 说「插入排序是 \(\Theta(n^2)\)」则要加定语「最坏 / 平均」.

常见量级

从小到大:

\[ O(1),\ O(\log n),\ O(\sqrt{n}),\ O(n),\ O(n\log n),\ O(n^2),\ O(n^3),\ O(2^n),\ O(n!) \]
量级 典型来源
\(O(1)\) 数组按下标访问, 栈的入栈 / 出栈
\(O(\log n)\) 折半查找
\(O(n)\) 遍历线性表, 插入排序最佳情况
\(O(n\log n)\) 堆排序、归并、快排平均情况
\(O(n^2)\) 插入 / 冒泡 / 简单选择的最坏情况
\(O(2^n)\) 朴素递归斐波那契
\(O(n!)\) 穷举全排列

算法分析里 \(\lg n\) 通常表示 \(\log_2 n\). \(\Theta(\lg n)\) 和 \(\Theta(\log_{10} n)\) 是一回事, 换底公式只差一个常数 \(\ln b\), 被 \(\Theta\) 吸收.

\(n\) 很小时, \(O(n^2)\) 的插入排序可以快过 \(O(n\log n)\) 的快排, 因为记号丢掉了常数. 复杂度比较的是 \(n\) 足够大 以后的趋势.

空间复杂度

空间复杂度 \(S(n)\) 描述算法耗费的存储随 \(n\) 的增长, 同样写成 \(S(n)=O(g(n))\).

通常只计辅助空间 (工作变量、辅助数组、递归调用栈), 不算存放输入本身的那份. 因此:

  • 只用几个临时变量: \(O(1)\), 也称原地算法. 直接插入、冒泡、堆排序都是

  • 归并需要 \(\Theta(n)\) 的临时数组

  • 递归快排平均栈深 \(O(\log n)\), 最坏 \(O(n)\)

若每层递归额外申请的空间不同, 要把各层加起来, 不能只看深度.

查找问题里还有一个专用指标: 平均查找长度 ASL, 本质仍是在数「关键字比较次数」的期望, 和 \(T(n)\) 是同一类想法.

排序算法的稳定性

评价排序算法时, 除了时间和空间, 还有一个指标称为稳定性（stability）.

若两个记录 \(R_1, R_2\) 关键字相同, 排序前 \(R_1\) 在 \(R_2\) 前面, 排完后 \(R_1\) 仍在 \(R_2\) 前面, 就称该算法稳定; 否则不稳定.

关键字往往不是记录的全部. 例如先按成绩排, 同分的人应保持原来的报名顺序; 基数排序从低位排到高位, 每一趟也必须稳定, 高位才能叠在低位次序上面.

怎么判断

稳定性是实现的性质, 不是算法名字自带的. 判定口诀: 相等时不要让后来者插队.

  • 要证不稳定, 举一个反例就够. 如希尔把 \(\{5_a, 5_b, 2\}\) 按增量 \(2\) 分组, \((5_a, 2)\) 排完变成 \(\{2, 5_b, 5_a\}\)

  • 要证稳定, 看相等时的动作: 直接插入 只在 a[i] > key 时后移; 归并 只在 left[i] <= right[j] 时取左. 改成 >= / <, 同一套流程就会变不稳定

内部排序算法稳定性速记

快选希堆不稳定. 其余常见内部排序默认稳定.

稳定 不稳定
直接插入、折半插入 希尔
冒泡 快排
归并、基数、计数 简单选择、堆排

\(O(n\log n)\) 的比较排序里, 只有归并稳定.