递推与分析工具
引入
词汇
| English | 释义 | 拼音 |
|---|---|---|
| algorithm design and analysis | 算法设计与分析 | suàn fǎ shè jì yǔ fēn xī |
| recurrence/rɪˈkʌrəns/ | 递推式 | dì tuī shì |
| recursion tree | 递归树 | dì guī shù |
树即分析
- 算法设计与分析 algorithm design and analysis 先定价再动手。递推式 recurrence 用更小的输入表达递归算法的代价：$T(n) = 2T(n/2) + \Theta(n)$。递归树 recursion tree 把它画出来：第 $i$ 层有 $2^i$ 个规模 $n/2^i$ 的节点、每层 $\Theta(n)$、深 $\log_2 n$——所以 $T(n) = \Theta(n \log n)$。
{exercise:uni-cs1001-tree}
练习
对 T(n) = 2T(n/2) + n，树的一层花费——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
第 i 层 2^i 个规模 n/2^i：乘积每层都是 n。
主定理三行版
- 对 $T(n) = aT(n/b) + f(n)$，把 $f(n)$ 与叶总量 $n^{\log_b a}$ 比较。叶胜：$\Theta(n^{\log_b a})$；平衡：$\Theta(f(n)\log n)$；根胜：$\Theta(f(n))$。
- 课程例：$2T(n/2) + n \to n\log n$；$T(n/2) + 1 \to \log n$；$4T(n/2) + n \to n^2$（叶 $n^{\log_2 4}$ 胜）。
{exercise:uni-cs1001-master}
练习
T(n) = 4T(n/2) + n 的解是——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
叶胜：n 的 log2 4 次方即 n²。
代入法证明
- 猜 $2T(n/2) + n$ 满足 $T(n) \le c\,n\log n$：代入后归纳在 $c \ge 1$ 时闭合——猜想升级为证明。
- 再测量：归并排序在固定 64 元课程数组上做 $310$ 次比较，低于最坏上界 $n\log_2 n - n + 1 = 321$。理论定界、实测确认。
{exercise:uni-cs1001-substitute}
练习
归并排序在 64 元课程数组上比较——次。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
实测 310，低于最坏上界 321 = 64×6 − 64 + 1。