Chap2 算法分析基础

返回：0400 算法设计与分析总目录 · 上一章：0401 Chap1 算法导论与稳定匹配 · 下一章：0403 Chap3 图算法基础

1、学习目标

算法分析回答两个问题：它是否正确，它是否足够快。本章主要处理第二个问题，建立运行时间的语言和估算习惯。

模块	要掌握的内容
可处理性	多项式时间、指数时间、输入规模
渐进记号	`O`、`Ω`、`Θ`
常见复杂度	`log n`、`n`、`n log n`、`n^2`、`2^n`
分析方法	循环计数、求和、递推、主定理直觉
证明习惯	先说明规模，再说明基本操作

2、输入规模

算法复杂度必须相对于输入规模讨论。

问题	输入规模
排序	元素个数 `n`
图遍历	顶点数 `n` 和边数 `m`
大整数乘法	数字位数 `n`
字符串匹配	文本长度 `n` 和模式长度 `m`
背包	物品数 `n` 和容量 `W`

不要看到一个循环就直接写 O(n)，要先问：n 是什么？

3、渐进记号

记号	含义	使用场景
`O(f(n))`	渐进上界	最常见，说明不会更慢太多
`Ω(f(n))`	渐进下界	说明至少需要这么多
`Θ(f(n))`	紧确界	上下界同阶
`o(f(n))`	严格低阶	比 `f(n)` 增长慢很多

常见增长顺序：

1	O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)

复盘时要能把常见算法放到这条线上。

4、常见运行时间

复杂度	常见来源
`O(1)`	数组下标、哈希期望查找
`O(log n)`	二分、平衡树高度
`O(n)`	单次扫描
`O(n log n)`	排序下界附近、分治每层线性
`O(n^2)`	双重比较、稠密图矩阵扫描
`O(n^3)`	Floyd、多层 DP
`O(2^n)`	子集枚举、回溯
`O(n!)`	排列枚举

多项式时间通常被视为“可处理”的基本边界，指数时间则往往只适合很小规模。

5、循环与求和

单层循环：

1	for (int i = 0; i < n; ++i) work();

复杂度 O(n)。

等差求和：

1
2
3

for (int i = 0; i < n; ++i) {
    for (int j = i; j < n; ++j) work();
}

次数为：

1	n + (n-1) + ... + 1 = Θ(n^2)

倍增循环：

1	for (int i = 1; i < n; i *= 2) work();

执行次数为 Θ(log n)。

6、递推分析

分治算法经常写成递推式：

递推式	代表算法	复杂度
`T(n)=T(n/2)+O(1)`	二分查找	`O(log n)`
`T(n)=2T(n/2)+O(n)`	归并排序	`O(n log n)`
`T(n)=T(n-1)+O(n)`	选择排序式递归	`O(n^2)`
`T(n)=2T(n/2)+O(1)`	某些树形合并	`O(n)`

主定理直觉：

1 2	T(n)=aT(n/b)+f(n) 比较 f(n) 和 n^(log_b a)

真正考试和复盘时，不必机械套公式，先画递归树通常更稳。

7、最好、最坏、平均、期望

类型	含义
最好情况	最幸运输入
最坏情况	所有输入中最慢
平均情况	对输入分布取平均
期望时间	对算法随机性取期望

快速排序是经典例子：

情况	复杂度
最好	`O(n log n)`
平均	`O(n log n)`
最坏	`O(n^2)`
随机化期望	`O(n log n)`

平均和期望不要混用：平均通常是输入分布，期望通常是算法内部随机性。

8、伪多项式

背包动态规划常写成 O(nW)。如果 W 是容量数值，这个复杂度对数值大小多项式，但对输入位数不是多项式。

1 2	W 的二进制长度约为 log W O(nW) 对 log W 来说是指数级

这种算法称为伪多项式算法。它在实际小容量时很好用，但不能说明问题属于强多项式可解。

9、复杂度写作模板

分析算法时可以按这个顺序写：

令输入规模为 n，若是图则令顶点数 |V|、边数 |E|。
说明主要循环或递归结构。
说明每一步的基本操作代价。
汇总求和或递推。
给出空间复杂度。

例：

1 2	BFS 每个顶点至多入队一次，每条边至多被检查常数次，因此邻接表实现的时间复杂度为 O(\|V\|+\|E\|)，空间复杂度为 O(\|V\|)。

10、易错点

易错点	修正
忽略输入规模定义	先定义 `n`、`m`、`W`
只数循环层数	内层次数可能变化
把平均和期望混用	平均看输入，期望看随机性
图算法只写 `O(n)`	通常要写 `O(	V	+	E	)`
伪多项式当成多项式	注意数值大小和编码长度

11、复盘清单

检查项	状态
能解释多项式时间为什么重要	待复盘
能区分 `O`、`Ω`、`Θ`	待复盘
能估计常见循环复杂度	待复盘
能画递归树分析归并排序	待复盘
能区分最坏、平均和期望时间	待复盘
能解释 `O(nW)` 为什么可能是伪多项式	待复盘