1.3 渐近界、递推式与摊还分析
完成常见复杂度分析后，用约 45 分钟走完分析步骤最后一层。这里会正式区分
O、Ω与Θ，把递归程序写成递推式，并说明 Master Theorem 能用和不能用的边界。
宽松的“不会超过”还不够
线性扫描既可以写成 O(n²)，也可以写成 O(2ⁿ)，但这两个上界都很松。只有一个正确上界不能说明真实增长速度，还要判断界是否紧。
1. O、Ω 与 Θ 是界，不是输入情况
设 f(n) 是选定成本模型下的非负成本函数，g(n) 在 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. 输出本身也会给出下界
生成所有无序位置对时，结果数量是
k = n(n - 1) / 2 = Θ(n²)若接口必须显式返回这 k 对，仅写出输出就需要 Ω(k) 时间和 Θ(k) 输出空间。换一种更聪明的循环不能把问题降成线性；除非接口改成只返回数量、惰性迭代器或压缩表示。不过，把迭代器中的全部 k 对消费完，仍需要 Ω(k) 时间；省掉的是提前保存所有结果的要求。
因此复杂度结论应写明：
- 输入规模；
- 成本模型；
- 最好、最坏、平均或期望情况；
- 输入、输出和辅助空间的口径；
- 依赖的容器、哈希或比较假设。
3. 递归程序先写递推式
在常数成本比较、按下标传递范围的前提下，二分查找最坏情况下递归到一半区间：
T(n) = T(n/2) + Θ(1) = Θ(log n)归并排序递归处理两个一半规模的子问题，再用线性时间合并：
T(n) = 2T(n/2) + Θ(n) = Θ(n log n)若暂把乘法计为一步，阶乘递归每次把 n 减一：
T(n) = T(n - 1) + Θ(1) = Θ(n)这里的递推式都在常数大小的输入处以 Θ(1) 结束，n/2 的取整不改变这些渐近结论。Python 阶乘的实际大整数运算需要另计位数，不能直接套用常数成本乘法。递推式里的非递归项必须包含当前调用真正做的工作。若切片会复制 k 个元素，不能把它当成 Θ(1)；若合并结果需要线性扫描，也不能只数递归调用。
4. 时间树和调用栈是两本账
时间分析累加所有调用做过的工作；栈空间只计算同一时刻尚未返回的调用。访问过很多节点，并不代表它们都同时留在栈上。
当 n 是 2 的幂时，归并排序有 log₂ n 层合并工作（另有一层叶子），每层合计处理 Θ(n) 个元素，所以总时间是 Θ(n log n)。但同一时刻只沿一条递归路径向下，递归栈深度是 Θ(log n)；合并缓冲区通常另需 Θ(n) 辅助空间。
朴素 Fibonacci 不一样：
def fib(n):
if n < 0:
raise ValueError("n must be non-negative")
if n < 2:
return n
return fib(n - 1) + fib(n - 2)它的调用树包含大量重复子问题。递归深度只有 Θ(n)，调用总数却按指数增长。把调用数记为 C(n)，可得 C(n) = 2F(n + 1) - 1，其中 F 是 Fibonacci 数；因此紧界是 Θ(φⁿ)，φ = (1 + √5) / 2，O(2ⁿ) 只是较松上界。看到两个递归分支时不能直接写 Θ(2ⁿ)；分支规模、是否剪枝和是否记忆化都会改变树的形状。
5. 三种常用求解方式
展开
T(n) = T(n/2) + c 展开 k 次后得到 T(n/2ᵏ) + kc。令 n/2ᵏ = 1，可得 k = log₂ n。
递归树
列出每层有多少子问题、每个子问题做多少非递归工作，再对所有层求和。它特别适合发现“每层都是 n”或“工作逐层增大”的结构。
代入验证
先根据展开或递归树猜一个界，再用归纳法验证常数确实存在。猜测不是证明；代入能暴露被忽略的低阶项和边界条件。
6. Master Theorem 只处理固定形状
经典形式是：
T(n) = aT(n/b) + f(n)其中 a ≥ 1、b > 1 为常数，子问题按相同比例缩小，f(n) 最终非负，常数规模的基本情况为 Θ(1)。记 p = log_b a。以下是常用版本的充分条件，ε 和 k 都必须是与 n 无关的常数：
| 关系 | 直觉 | 典型结论 |
|---|---|---|
| f(n) = O(n^(p−ε))，ε > 0 | 叶子/子问题工作主导 | Θ(n^p) |
| f(n) = Θ(n^p log^k n)，k ≥ 0 | 各层工作相加 | Θ(n^p log^(k+1) n) |
| f(n) = Ω(n^(p+ε))，ε > 0，且 a·f(n/b) ≤ c·f(n)，某个 c < 1 对充分大的 n 成立 | 根部工作主导；后半句是正则条件 | Θ(f(n)) |
三个例子：
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改变。
可以先用展开、递归树或代入。对 T(n/3) + T(2n/3) 这种固定比例但大小不同的子问题，还可在满足条件时用 Akra–Bazzi 方法；它并不自动适用于 n−1 型递归。另如 f(n) = n^p / log n，也不在上表 k ≥ 0 的第二种情况内。
7. 用调用次数核对递推直觉
保存为 recurrence_demo.py：
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 == [size * (size.bit_length() - 1) 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()python3 recurrence_demo.py预期输出：
fib(10)：55
朴素 Fibonacci 调用数：177
归并层工作：{1: 0, 2: 2, 4: 8, 8: 24, 16: 64}
递推式检查通过fib_with_calls 真正执行递归调用并统计节点。merge_work 则只计算模型工作量：它把一个子结果乘以 2，没有实际排序、扫描 n 个元素或执行两次递归，因此返回 n log₂ n 不代表函数自身耗时 Θ(n log n)。这些具体规模验证公式取值，不替代渐近证明。
8. 摊还成本不需要概率分布
动态数组追加时，大多数操作只写入一个位置；容量不足的那次却要申请更大数组并复制旧元素。从空数组开始且容量按几何比例增长，前 n 次追加的总复制量形成几何级数，总成本仍是 Θ(n)，所以每次追加的摊还成本为 Θ(1)。
这不表示每次最坏成本是常数，也不是对随机输入求平均。摊还分析研究的是任意合法操作序列的总成本，常用三种视角：
- 聚合法：先算整段操作的总成本；
- 记账法：便宜操作预存“余额”，支付未来昂贵操作；
- 势能法：用状态势能表示已经积累的待付工作。
9. 复杂度与基准测试回答不同问题
复杂度分析解释输入增长时模型工作量的趋势；基准测试观察某个实现、运行时、机器和输入分布下的实际表现。两者都需要：
- 复杂度不会告诉你缓存、向量化、对象布局和常数因子；
- 一次计时也无法证明渐近界；
- 小输入上，简单的
Θ(n²)实现可能胜过常数很大的Θ(n log n)实现； - 工程决策应先排除增长阶明显不合适的方案，再用代表性负载测量候选实现。
离开分析步骤前，写全一份分析
任选一个递归函数，写明输入规模、成本模型、递推式、边界条件、求解方法、时间紧界、递归栈与其他辅助空间。若使用 Master Theorem，还要逐项证明 a、b、f(n) 和适用条件成立。
再把接口改成返回全部结果，检查输出大小是否给出新的下界。最后说明结论属于最好、最坏、平均、期望还是摊还成本。五个标签不应互相替代。
查阅正式定义与标准算法
- MIT 6.006：Asymptotic notation。
- Open Data Structures。
- Python Wiki：TimeComplexity：分析 Python 容器操作时核对实现假设。
继续学习：连续格子与节点路径
你已经有了时间、空间和输出规模三把尺子。下一章比较数组的连续存放与链表的节点连接，并把这里的每条分析规则落到访问、插入、删除和遍历上。