渐近分析
引入
词汇
| English | 释义 | 拼音 |
|---|---|---|
| data structures and algorithms | 数据结构与算法 | shù jù jié gòu yǔ suàn fǎ |
| Big-O/bɪɡ əʊ/ | 大O记号 | dà O jì hào |
| Big-Θ | 大Θ记号 | dà Θ jì hào |
度量的标尺
- 数据结构与算法 data structures and algorithms 就是按输入增长时的代价来选容器、选做法。大O记号 Big-O 从上方界定增长（相差至多一个常数）；下界孪生兄弟是大Ω；大Θ记号 Big-Θ 钉住确切增长率。
- 丢掉常数与低阶项：$3n^2 + 5n + 7$ 就是 $\Theta(n^2)$——在 $n = 1000$ 处，$n \log_2 n \approx 9\,966$ 对 $n^2 = 10^6$：约 $100$ 倍之差。
{exercise:uni-cs0501-classes}
练习
3n^2 + 5n + 7 属于——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
丢掉常数与低阶项，n 平方项吞掉其余。
增长表
- $n = 10 / 100 / 1000$ 时：$\log_2 n$ 读作 $3 / 7 / 10$；$n \log_2 n$ 读作 $33 / 664 / 9\,966$；$n^2$ 读作 $100 / 10^4 / 10^6$；$2^{100} \approx 10^{30}$。
- 折半产生对数：每步把 $n$ 减半的算法只碰 $\log_2 n$ 层——$16$ 个元素上二分查找至多 $4$ 次探测，因为 $2^4 = 16$。
{exercise:uni-cs0501-log}
练习
每步把输入减半的算法会碰——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
每次折半算一步：16 个元素 4 次探测，因为 2 的 4 次方是 16。
倍增测量法
- $n = 100$ 的两个循环：单层执行 $100$ 次，嵌套执行 $100 \times 100 = 10\,000$ 次。$n$ 翻倍：线性变 $200$，嵌套翻两番变 $40\,000$。
- 倍增测得的比值就是指数：$2$ 是线性，$4$ 是平方。从未数过的代价主张，不要相信。
例子
每轮折半 i 的循环是 $\Theta(\log n)$；先后两个 $n$ 循环相加为 $\Theta(n)$；折半循环里套一个 $n$ 循环相乘为 $\Theta(n \log n)$——归并排序的形状。
{exercise:uni-cs0501-double}
练习
n 翻倍、计数翻两番，指数是——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
倍增比值即指数：4 就是平方。