数据结构与算法 / 系统课时

递归树方法

递归树方法

上一课用代入法验证递推式。本课把每个递归调用画成一个节点,只在节点上记录本次非递归工作。把各层和叶子合计,可以得到闭式,或推导规模足够大时的上下界。

学习目标

  • 区分节点成本、层成本、树高和叶子成本。
  • 对等规模拆分写出第 ii 层的贡献,并核对精确闭式。
  • 对整数取整与不等深的分支分别建立上下界。

等规模树怎样计费

设 n=bhn=b^h、T(1)=Θ(1)T(1)=\Theta(1),递推为 T(n)=aT(n/b)+f(n)T(n)=aT(n/b)+f(n)。根深度为 0。每个内部节点分出 aa 个子问题,深度 i<hi<h 有 aia^i 个节点、规模 n/bin/b^i,这一层花费 aif(n/bi)a^i f(n/b^i)。深度 hh 是叶子层,成本为 ahT(1)a^hT(1)。树高按边数是 hh,层数是 h+1h+1。 MIT 递归树与主定理资料

递归树每层成本与树高

取 a=b=2a=b=2、f(n)=nf(n)=n、T(1)=1T(1)=1。每个内部层的工作为 2i(n/2i)=n2^i(n/2^i)=n,共 log⁡2n\log_2 n 层。每个叶子代价 1,有 nn 个,所以 T(n)=nlog⁡2n+nT(n)=n\log_2 n+n。这对 n=1n=1 也成立,该情形没有内部层。比较渐进阶时,n≥2n≥2 可写成 Θ(nlog⁡n)\Theta(n\log n)。如果改为 f(n)=n2f(n)=n^2,内部层成本变成 n2/2in^2/2^i,求和时应按几何级数处理。 MIT 递推展开

取整不能省略证明

实际拆分可得到 T(n)=T(⌊n/2⌋)+T(⌈n/2⌉)+nT(n)=T(\lfloor n/2\rfloor)+T(\lceil n/2\rceil)+n。两侧规模之和仍为 nn,但各分支可能在不同深度结束。在深度小于 ⌊log⁡2n⌋\lfloor\log_2 n\rfloor 的层上,每个节点都至少为 2,规模之和为 nn,因此内部层成本有 n⌊log⁡2n⌋n\lfloor\log_2 n\rfloor 的下界。每层规模之和不超过 nn,树高不超过 ⌈log⁡2n⌉\lceil\log_2 n\rceil,叶子代价合计 nn。这给出同阶上界。对三分之一和三分之二等更不平衡的拆分,也应重新检查层的覆盖范围与叶子成本。 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 个叶子。计算通用上界时,若已单独计入全部叶子,就只对内部节点求各层成本,避免重复。

本课练习

对 4T(n/2)+n4T(n/2)+n 写出前三层成本和叶子数,再分析 2T(n/2)+n22T(n/2)+n^2 的内部层总和。下一课会说明哪些层成本可以用主定理直接判断。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

递归树方法

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通