读《算法导论》第三章笔记 —— 函数的增长
这一章是后面分析所有算法复杂度的基础工具。之前学的时候只是机械地记忆 O(n) / O(n log n) 这些符号，这次重读才意识到三个记号的精确定义其实非常对称漂亮。
三个渐进记号的定义
O(g(n))：存在 c > 0 和 n₀，使得对所有 n ≥ n₀，0 ≤ f(n) ≤ c·g(n)。
Ω(g(n))：存在 c > 0 和 n₀，使得对所有 n ≥ n₀，0 ≤ c·g(n) ≤ f(n)。
Θ(g(n))：同时是 O(g(n)) 和 Ω(g(n))。
注意三个记号都是集合，f(n) ∈ O(g(n)) 才严谨，写 f(n) = O(g(n)) 是约定俗成的滥用。理解这一点之后很多教材里类似 n + O(1) 这种表达就好懂了：右边是个集合，整个式子是说 f(n) - n 落在这个集合里。
常见误区
O 是上界，Ω 是下界，Θ 是紧确界。但"算法的最坏情况是 O(n²)"这句话完全没问题，因为最坏情况本身就是上界估计。把 O 和"最坏"绑定起来理解是错的，O 只描述函数增长速度，跟"最好/最坏/平均"哪种情况无关。
函数增长率的几个例子
书里 3.2 节的练习题做了一些，记一下结果：
n^0.5 < log n ? 错，反过来：log n < n^0.5
2^n vs n! n! 增长更快（用 Stirling 公式）
log²n vs n^0.5 n^0.5 更快
n log n vs n^(1+ε) 任意 ε > 0，后者更快记忆这些不如建立直觉：多项式 ≪ 指数 ≪ 阶乘，对数比任何多项式都慢。
主方法（master theorem）预告
后面 4.5 节会用主方法快速求解递归式。这一章的渐进记号是为它做铺垫。简记三种情况：
- 非递归部分占主导 → T(n) = Θ(f(n))
- 递归与非递归部分量级相同 → T(n) = Θ(f(n) log n)
- 递归部分占主导 → T(n) = Θ(n^log_b a)
到时候再细看。
小结
这一章看似数学，但读完会发现它其实是给后面所有复杂度证明提供"语言"。把定义理解到能脱离例子也写出来的程度，后面才不会卡住。
← 返回首页