数据结构与算法 / 系统课时
递归树方法
递归树方法
上一课用代入法验证递推式。本课把每个递归调用画成一个节点,只在节点上记录本次非递归工作。把各层和叶子合计,可以得到闭式,或推导规模足够大时的上下界。
学习目标
- 区分节点成本、层成本、树高和叶子成本。
- 对等规模拆分写出第 层的贡献,并核对精确闭式。
- 对整数取整与不等深的分支分别建立上下界。
等规模树怎样计费
设 、,递推为 。根深度为 0。每个内部节点分出 个子问题,深度 有 个节点、规模 ,这一层花费 。深度 是叶子层,成本为 。树高按边数是 ,层数是 。 MIT 递归树与主定理资料

取 、、。每个内部层的工作为 ,共 层。每个叶子代价 1,有 个,所以 。这对 也成立,该情形没有内部层。比较渐进阶时, 可写成 。如果改为 ,内部层成本变成 ,求和时应按几何级数处理。 MIT 递推展开
取整不能省略证明
实际拆分可得到 。两侧规模之和仍为 ,但各分支可能在不同深度结束。在深度小于 的层上,每个节点都至少为 2,规模之和为 ,因此内部层成本有 的下界。每层规模之和不超过 ,树高不超过 ,叶子代价合计 。这给出同阶上界。对三分之一和三分之二等更不平衡的拆分,也应重新检查层的覆盖范围与叶子成本。 MIT 递推与取整
用 Python 对照层成本和递推
把下面保存为 recursion_tree_demo.py,用 Python 3.11 或以上运行。对奇数实际使用整除后取余的一半。代码展开每个调用来核对计数,适合小规模实验。
python
def layer_costs(n: int) -> list[int]:
if type(n) is not int or n < 1:
raise ValueError("n must be a positive integer")
totals: list[int] = []
def visit(size: int, depth: int) -> None:
if depth == len(totals):
totals.append(0)
totals[depth] += size # 叶子规模 1,成本也为 1
if size > 1:
left = size // 2
visit(left, depth + 1)
visit(size - left, depth + 1)
visit(n, 0)
return totals
def recurrence_cost(n: int) -> int:
if type(n) is not int or n < 1:
raise ValueError("n must be a positive integer")
def solve(size: int) -> int:
if size == 1:
return 1
return size + solve(size // 2) + solve(size - size // 2)
return solve(n)
for n in (1, 2, 4, 7, 8, 16):
levels = layer_costs(n)
total = sum(levels)
assert total == recurrence_cost(n)
if n & (n - 1) == 0:
assert total == n * n.bit_length()
print(f"n={n}: {levels} => {total}")text
n=1: [1] => 1
n=2: [2, 2] => 4
n=4: [4, 4, 4] => 12
n=7: [7, 7, 7, 6] => 27
n=8: [8, 8, 8, 8] => 32
n=16: [16, 16, 16, 16, 16] => 80规模 7 的第一批叶子在倒数第二层,因此该层的 7 包含叶子和内部节点两种成本,最后一层只剩 6 个叶子。计算通用上界时,若已单独计入全部叶子,就只对内部节点求各层成本,避免重复。
本课练习
对 写出前三层成本和叶子数,再分析 的内部层总和。下一课会说明哪些层成本可以用主定理直接判断。
按自己的节奏,确认真正理解。