Software Systems Atlas

中文

English

中文

English

主题

1.3 渐近界、递推式与摊还分析 ​

完成常见复杂度分析后，用约 45 分钟走完瞭望台最后一层。这里会正式区分 O、Ω 与 Θ，把递归程序写成递推式，并说明 Master Theorem 能用和不能用的边界。

地图上的“不会超过”还不够 ​

前两层瞭望台教你定义输入规模、数模型操作，并从循环范围写出表达式。老陈在最后一层摊开三张地图：第一张只标“不会比这条路更长”，第二张只标“至少要走这么远”，第三张同时给出上下边界。

三张地图都可能正确，却回答不同问题。若一个线性扫描既可以写成 O(n²)，也可以写成 O(2ⁿ)，只有一个宽松上界并不能说明它真正按什么速度增长。

1. O、Ω 与 Θ 是界，不是输入情况 ​

设 f(n) 是选定成本模型下的非负成本函数。

  • f(n) = O(g(n))：存在正常数 c 和阈值 n₀，使所有 n ≥ n₀ 都满足 f(n) ≤ c·g(n)。
  • f(n) = Ω(g(n))：存在正常数 c 和阈值 n₀，使所有 n ≥ n₀ 都满足 f(n) ≥ c·g(n)。
  • f(n) = Θ(g(n))：同时存在渐近上界和下界；也就是最终被两个常数倍的 g(n) 夹住。

3n + 7 属于 Θ(n)，也属于 O(n²)。前者给出紧界，后者只是正确但较松的上界。

最好、最坏和平均情况是另一条轴。线性查找可以有：

输入情况成本函数紧界
最好：第一项命中1Θ(1)
最坏：末尾命中或不存在nΘ(n)
平均取决于目标位置与缺失概率必须先给分布

“最坏情况是大 O、最好情况是 Ω”不是定义。你可以给最坏成本写 Θ(n)，也可以给最好成本写 O(1)。

2. 输出本身也会给出下界 ​

生成所有无序位置对时，结果数量是

text
k = n(n - 1) / 2 = Θ(n²)

若接口必须显式返回这 k 对，仅写出输出就需要 Ω(k) 时间和 Θ(k) 输出空间。换一种更聪明的循环不能把问题降成线性；除非需求改成只返回数量、迭代器或压缩表示。

因此复杂度结论应写明：

  1. 输入规模；
  2. 成本模型；
  3. 最好、最坏、平均或期望情况；
  4. 输入、输出和辅助空间的口径；
  5. 依赖的容器、哈希或比较假设。

3. 递归程序先写递推式 ​

算法森林里的路开始分叉。你每走到一个节点，就把问题拆成几条更小的路，还要付出整理和合并的代价。此时只盯着一层循环会漏掉整棵调用树；先把“分几支、每支多大、本层做多少事”写成递推式。

二分查找每次只递归到一半区间，并做常数额外工作：

text
T(n) = T(n/2) + Θ(1) = Θ(log n)

归并排序递归处理两个一半规模的子问题，再用线性时间合并：

text
T(n) = 2T(n/2) + Θ(n) = Θ(n log n)

阶乘递归每次只把 n 减一：

text
T(n) = T(n - 1) + Θ(1) = Θ(n)

递推式里的非递归项必须包含当前调用真正做的工作。若切片会复制 k 个元素，不能把它当成 Θ(1)；若合并结果需要线性扫描，也不能只数递归调用。

4. 时间树和调用栈是两本账 ​

老陈在地图旁放了两本记录：一本统计整片森林总共走过多少路，另一本只记背包里同时压着几层未返回的路线。前者是总工作量，后者才对应递归调用栈。

归并排序的递归树有 log₂ n 层，每层合计处理 Θ(n) 个元素，所以总时间是 Θ(n log n)。但同一时刻只沿一条递归路径向下，递归栈深度是 Θ(log n)；合并缓冲区通常另需 Θ(n) 辅助空间。

朴素 Fibonacci 不一样：

python
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

它的调用树包含大量重复子问题。递归深度只有 Θ(n)，调用总数却按指数增长。看到两个递归分支时不能直接写 Θ(2ⁿ)；分支规模、是否剪枝和是否记忆化都会改变树的形状。

5. 三种常用求解方式 ​

展开 ​

T(n) = T(n/2) + c 展开 k 次后得到 T(n/2ᵏ) + kc。令 n/2ᵏ = 1，可得 k = log₂ n。

递归树 ​

列出每层有多少子问题、每个子问题做多少非递归工作，再对所有层求和。它特别适合发现“每层都是 n”或“工作逐层增大”的结构。

代入验证 ​

先根据展开或递归树猜一个界，再用归纳法验证常数确实存在。猜测不是证明；代入能暴露被忽略的低阶项和边界条件。

6. Master Theorem 只处理固定形状 ​

经典形式是：

text
T(n) = aT(n/b) + f(n)

其中 a ≥ 1、b > 1 为常数，子问题规模相同。先比较 f(n) 与 n^(log_b a)。

关系直觉典型结论
f(n) 多项式意义上更小叶子/子问题工作主导Θ(n^(log_b a))
f(n) 同阶，可能带对数因子各层工作接近多一个对数因子
f(n) 多项式意义上更大，且满足正则条件根部非递归工作主导Θ(f(n))

三个例子：

text
8T(n/2) + Θ(n²)  -> Θ(n³)
2T(n/2) + Θ(n)   -> Θ(n log n)
2T(n/2) + Θ(n²)  -> Θ(n²)

不能直接套用的常见情况：

  • T(n) = T(n - 1) + Θ(1)：子问题不是按固定比例缩小；
  • T(n) = T(n/3) + T(2n/3) + Θ(n)：子问题大小不同；
  • 朴素 Fibonacci：T(n-1) + T(n-2) + Θ(1)；
  • 分支数或缩小比例随 n 改变。

这时可用展开、递归树、代入，或更一般的 Akra–Bazzi 方法。公式的适用条件比背三种情况更重要。

7. 用调用次数核对递推直觉 ​

保存为 recurrence_demo.py：

python
from math import log2


def fib_with_calls(n: int) -> tuple[int, int]:
    if n < 0:
        raise ValueError("n must be non-negative")
    if n < 2:
        return n, 1
    left, left_calls = fib_with_calls(n - 1)
    right, right_calls = fib_with_calls(n - 2)
    return left + right, 1 + left_calls + right_calls


def merge_work(n: int) -> int:
    if n < 1 or n & (n - 1):
        raise ValueError("n must be a positive power of two")
    if n == 1:
        return 0
    return 2 * merge_work(n // 2) + n


def main() -> None:
    fib_value, fib_calls = fib_with_calls(10)
    sizes = [1, 2, 4, 8, 16]
    work = [merge_work(size) for size in sizes]

    assert fib_value == 55
    assert fib_calls == 177
    assert work == [int(size * log2(size)) for size in sizes]

    print(f"fib(10)：{fib_value}")
    print(f"朴素 Fibonacci 调用数：{fib_calls}")
    print(f"归并层工作：{dict(zip(sizes, work))}")
    print("递推式检查通过")


if __name__ == "__main__":
    main()
bash
python3 recurrence_demo.py

预期输出：

text
fib(10)：55
朴素 Fibonacci 调用数：177
归并层工作：{1: 0, 2: 2, 4: 8, 8: 24, 16: 64}
递推式检查通过

计数程序只验证这些具体规模符合推导，不替代渐近证明。它的价值是把递归树中的“节点数”和“每层工作”变成可检查数据。

8. 摊还成本不需要概率分布 ​

森林里的伸缩桥平时只添一块木板，容量耗尽时却要把整座桥搬到更大的基座。某一次扩容很贵，不代表每一步平均都贵；把一整段确定操作的总账摊回每次操作即可。

动态数组追加时，大多数操作只写入一个位置；容量不足的那次却要申请更大数组并复制旧元素。若容量按几何比例增长，前 n 次追加的总复制量形成几何级数，总成本仍是 Θ(n)，所以每次追加的摊还成本为 Θ(1)。

这不表示每次最坏成本是常数，也不是对随机输入求平均。摊还分析研究的是任意合法操作序列的总成本，常用三种视角：

  • 聚合法：先算整段操作的总成本；
  • 记账法：便宜操作预存“余额”，支付未来昂贵操作；
  • 势能法：用状态势能表示已经积累的待付工作。

9. 复杂度与基准测试回答不同问题 ​

复杂度分析解释输入增长时模型工作量的趋势；基准测试观察某个实现、运行时、机器和输入分布下的实际表现。两者都需要：

  • 复杂度不会告诉你缓存、向量化、对象布局和常数因子；
  • 一次计时也无法证明渐近界；
  • 小输入上，简单的 Θ(n²) 实现可能胜过常数很大的 Θ(n log n) 实现；
  • 工程决策应先排除增长阶明显不合适的方案，再用代表性负载测量候选实现。

离开瞭望台前，写全一份分析 ​

任选一个递归函数，写明输入规模、成本模型、递推式、边界条件、求解方法、时间紧界、递归栈与其他辅助空间。若使用 Master Theorem，还要逐项证明 a、b、f(n) 和适用条件成立。

再把接口改成返回全部结果，检查输出大小是否给出新的下界。最后说明结论属于最好、最坏、平均、期望还是摊还成本。五个标签不应互相替代。

查阅正式定义与标准算法 ​

下一站：连续格子与节点小径 ​

你已经有了时间、空间和输出规模三把尺子。下一章比较数组的连续存放与链表的节点连接，并把这里的每条分析规则落到访问、插入、删除和遍历上。

继续学习数组

Built with VitePress | Software Systems Atlas

Copyright 2026 Steven Yang