7.3 分治递推与递归树

第 7.2 节把数列的一项连接到较早的项。现在我们回到第 5 章研究过的算法代价函数。

递归算法通过在更小的输入上调用自身来解决问题。若输入规模为 $n$ ，操作次数就不能只靠一个循环来统计，因为总代价还包含每一个递归调用所做的工作。

递推关系可以完整记录这套依赖结构。

从算法写出代价递推式

一个分治算法包含三个概念阶段：

1. 分解：把输入拆成更小的子问题； 2. 解决：递归求解各个子问题； 3. 合并：把子问题答案组合为原问题答案。

用 $T(n)$ 表示求解规模为 $n$ 的输入所需的代价。常见的递推形式是

T(n)=aT\!\left(\frac{n}{b}\right)+f(n).

每个符号都有明确含义：

$a$ 是一次非基础调用产生的递归子问题数量；
$b$ 是每个子问题的规模缩小倍数；
因此 $n/b$ 是每个子问题的规模；
$f(n)$ 是当前调用执行的非递归分解与合并工作。

我们假设 $a\ge1$ 且 $b>1$ 。为了让最初的计算保持精确，通常先假设 $n$ 是 $b$ 的整数次幂。加入向下或向上取整会改变端点细节，但通常不会改变渐近类别。

递推式还需要一个基础代价。这里使用

T(1)=d,

其中 $d>0$ 是常数。

例子：二分查找只产生一个更小调用

二分查找把目标与数组中间元素比较，然后只在其中一半继续。若比较与更新下标共花费常数代价 $c$ ，则

T(n)=T\!\left(\frac n2\right)+c,qquad T(1)=d.

展开一次：

T(n)=\left[T\!\left(\frac n4\right)+c\right]+c =T\!\left(\frac n4\right)+2c.

展开 $i$ 次后，

T(n)=T\!\left(\frac{n}{2^i}\right)+ic.

当

\frac{n}{2^i}=1

时到达基础情况。因此 $2^i=n$ ，即

i=\log_2 n.

代回得到

T(n)=d+c\log_2 n\in\Theta(\log n).

这就是第 5 章“反复减半循环”的递归表达。

递归树展示每一次调用

连续进行代数展开容易隐藏工作发生在哪里。递归树使用以下对应：

一个结点表示一次递归调用；
结点的孩子表示它产生的递归子调用；
结点上的代价标签表示该调用的非递归工作。

对

T(n)=aT\!\left(\frac nb\right)+f(n),

第 $0$ 层只有原始调用，第 $1$ 层包含它的孩子，之后依次向下。

在第 $i$ 层：

结点数量为 $a^i$ ；
每个结点处理的规模为 $n/b^i$ ；
每个结点贡献 $f(n/b^i)$ 的非递归工作；
因此这一层的非递归总代价为

C_i=a^i f\!\left(\frac{n}{b^i}\right).

当 $n/b^h=1$ 时到达叶子。解得树高

h=\log_b n.

叶子数量是

a^h=a^{\log_b n}=n^{\log_b a}.

恒等式 $a^{\log_b n}=n^{\log_b a}$ 把叶子数写成 $n$ 的幂。指数 $\log_b a$ 衡量了输入不断缩小时，递归需求增长得有多快。

例子：归并排序每个内部层的工作量相等

归并排序产生两个规模为 $n/2$ 的子问题，并在线性时间内合并两个有序结果。其递推式为

T(n)=2T\!\left(\frac n2\right)+cn,qquad T(1)=d.

在第 $i$ 层：

有 $2^i$ 次调用；
每次调用处理 $n/2^i$ 个元素；
每次调用执行 $c(n/2^i)$ 的合并工作。

所以该层代价为

C_i =2^i\cdot c\frac{n}{2^i} =cn.

内部层共有 $\log_2 n$ 层。把相同的层代价相加：

\sum_{i=0}^{\log_2 n-1}cn =cn\log_2 n.

叶子有 $2^{\log_2 n}=n$ 个，每个代价为 $d$ ，所以叶子总代价为 $dn$ 。最终

T(n)=cn\log_2 n+dn\in\Theta(n\log n).

因子 $n$ 来自单层的工作量，因子 $\log n$ 来自层数。

正在加载交互实验...

导演一场递归树动画：每次只展开一层，检查每次调用的输入规模和局部代价，再看所有结点汇总成当层的代价条。二分查找、归并排序和四路递归三个场景会分别呈现单路径、逐层平衡和叶子爆发。

正在加载概念检查...

正在加载本节练习...

递归树代价的三种分布方式

总代价等于所有层代价与叶子代价之和。根据递推式的不同，大部分工作可能集中在根附近、均匀分布于每层，或者在靠近叶子的地方迅速累积。

假设非递归工作是幂函数

f(n)=cn^d,

其中 $c>0$ 且 $d\ge0$ 。第 $i$ 层有

\begin{aligned} C_i &=a^i c\left(\frac{n}{b^i}\right)^d\\ &=cn^d\left(\frac{a}{b^d}\right)^i. \end{aligned}

比值

\rho=\frac{a}{b^d}

说明代价从一层到下一层怎样变化。

根部占优： $\rho<1$

若 $a<b^d$ ，层代价按等比数列缩小，顶部几层占主导，因此

T(n)\in\Theta(n^d).

例如：

T(n)=2T(n/2)+n^2.

这里 $a=2$ 、 $b=2$ 、 $d=2$ ，所以 $\rho=2/4=1/2$ 。

逐层平衡： $\rho=1$

若 $a=b^d$ ，每个内部层具有相同的渐近代价。再乘以层数可得

T(n)\in\Theta(n^d\log n).

归并排序中 $a=2$ 、 $b=2$ 、 $d=1$ ，所以 $\rho=1$ 。

叶子占优： $\rho>1$

若 $a>b^d$ ，层代价按等比数列增长，树的底部占主导，而叶子数量决定最终阶数：

T(n)\in\Theta\!\left(n^{\log_b a}\right).

对

T(n)=4T(n/2)+n,

有 $\rho=4/2=2$ 。叶子数量为

n^{\log_2 4}=n^2,

所以 $T(n)\in\Theta(n^2)$ 。

简化版主定理

上面三种比较构成了一个实用的主定理版本。对

T(n)=aT(n/b)+\Theta(n^d),

其中 $a\ge1$ 、 $b>1$ 、 $d\ge0$ ，并满足常规正则条件，比较 $d$ 与 $\log_b a$ ：

T(n)= \begin{cases} \Theta\!\left(n^{\log_b a}\right), & d<\log_b a,\\[4pt] \Theta(n^d\log n), & d=\log_b a,\\[4pt] \Theta(n^d), & d>\log_b a. \end{cases}

这个版本覆盖多项式形式的合并代价。更一般的主定理还可以处理对数因子，并需要更精确的条件；本节暂时不需要这些扩展。

有纪律的使用步骤

面对一个新递推式：

1. 从算法中识别 $a$ 、 $b$ 和 $f(n)$ ； 2. 写明基础情况； 3. 若 $f(n)=\Theta(n^d)$ ，计算 $d$ 与 $\log_b a$ ； 4. 选择相应情况； 5. 用递归树的层代价检查结论。

最后一步很重要。死记某个“第几种情况”很容易出错，而递归树能解释答案为什么具有该增长率。

主定理不能直接处理哪些递推式

上面展示的形式不能直接处理所有递推式。例如，

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

的子问题规模是 $n-1$ ，而不是 $n/b$ ；又如

T(n)=T(n/3)+T(2n/3)+n

的两个子问题规模并不相等。

这些递推式仍然可以用展开、代入或更一般的递归树方法分析。定理是带有前提条件的工具，不能只凭外观套公式。

正在加载交互实验...

在工作量竞技场中调整分支数 $a$ 、缩小倍数 $b$ 和合并指数 $d$ 。递归需求与局部工作沿同步层级竞速；揭晓前，你要先把预测放到“根部占优”“逐层平衡”或“叶子占优”。随后竞技场才显示比值 $a/b^d$ 与对应的渐近证明书。

正在加载概念检查...

正在加载本节练习...

注意

不能只根据递归调用数量判断分治算法的界。必须统计每层工作量、层数，并把叶子代价包括进来。

本章衔接

第 7 章把构造、计数、证明与算法连接起来：递归定义生成合法对象，结构归纳跟随构造规则，递推关系统计较小情况，递归树则汇总递归算法的全部工作。

第 8 章将转向整数。整除与素因数分解会为模运算和密码学提供结构，而递归推理也会再次出现在欧几里得算法中。

7.3 分治递推与递归树

第 7.2 节把数列的一项连接到较早的项。现在我们回到第 5 章研究过的算法代价函数。

递推关系可以完整记录这套依赖结构。

从算法写出代价递推式

一个分治算法包含三个概念阶段：

1. 分解：把输入拆成更小的子问题； 2. 解决：递归求解各个子问题； 3. 合并：把子问题答案组合为原问题答案。

用 $T(n)$ 表示求解规模为 $n$ 的输入所需的代价。常见的递推形式是

T(n)=aT\!\left(\frac{n}{b}\right)+f(n).

每个符号都有明确含义：

$a$ 是一次非基础调用产生的递归子问题数量；
$b$ 是每个子问题的规模缩小倍数；
因此 $n/b$ 是每个子问题的规模；
$f(n)$ 是当前调用执行的非递归分解与合并工作。

递推式还需要一个基础代价。这里使用

T(1)=d,

其中 $d>0$ 是常数。

例子：二分查找只产生一个更小调用

二分查找把目标与数组中间元素比较，然后只在其中一半继续。若比较与更新下标共花费常数代价 $c$ ，则

T(n)=T\!\left(\frac n2\right)+c,qquad T(1)=d.

展开一次：

T(n)=\left[T\!\left(\frac n4\right)+c\right]+c =T\!\left(\frac n4\right)+2c.

展开 $i$ 次后，

T(n)=T\!\left(\frac{n}{2^i}\right)+ic.

当

\frac{n}{2^i}=1

时到达基础情况。因此 $2^i=n$ ，即

i=\log_2 n.

代回得到

T(n)=d+c\log_2 n\in\Theta(\log n).

这就是第 5 章“反复减半循环”的递归表达。

递归树展示每一次调用

连续进行代数展开容易隐藏工作发生在哪里。递归树使用以下对应：

一个结点表示一次递归调用；
结点的孩子表示它产生的递归子调用；
结点上的代价标签表示该调用的非递归工作。

对

T(n)=aT\!\left(\frac nb\right)+f(n),

第 $0$ 层只有原始调用，第 $1$ 层包含它的孩子，之后依次向下。

在第 $i$ 层：

结点数量为 $a^i$ ；
每个结点处理的规模为 $n/b^i$ ；
每个结点贡献 $f(n/b^i)$ 的非递归工作；
因此这一层的非递归总代价为

C_i=a^i f\!\left(\frac{n}{b^i}\right).

当 $n/b^h=1$ 时到达叶子。解得树高

h=\log_b n.

叶子数量是

a^h=a^{\log_b n}=n^{\log_b a}.

恒等式 $a^{\log_b n}=n^{\log_b a}$ 把叶子数写成 $n$ 的幂。指数 $\log_b a$ 衡量了输入不断缩小时，递归需求增长得有多快。

例子：归并排序每个内部层的工作量相等

归并排序产生两个规模为 $n/2$ 的子问题，并在线性时间内合并两个有序结果。其递推式为

T(n)=2T\!\left(\frac n2\right)+cn,qquad T(1)=d.

在第 $i$ 层：

有 $2^i$ 次调用；
每次调用处理 $n/2^i$ 个元素；
每次调用执行 $c(n/2^i)$ 的合并工作。

所以该层代价为

C_i =2^i\cdot c\frac{n}{2^i} =cn.

内部层共有 $\log_2 n$ 层。把相同的层代价相加：

\sum_{i=0}^{\log_2 n-1}cn =cn\log_2 n.

叶子有 $2^{\log_2 n}=n$ 个，每个代价为 $d$ ，所以叶子总代价为 $dn$ 。最终

T(n)=cn\log_2 n+dn\in\Theta(n\log n).

因子 $n$ 来自单层的工作量，因子 $\log n$ 来自层数。

正在加载交互实验...

正在加载概念检查...

正在加载本节练习...

递归树代价的三种分布方式

总代价等于所有层代价与叶子代价之和。根据递推式的不同，大部分工作可能集中在根附近、均匀分布于每层，或者在靠近叶子的地方迅速累积。

假设非递归工作是幂函数

f(n)=cn^d,

其中 $c>0$ 且 $d\ge0$ 。第 $i$ 层有

\begin{aligned} C_i &=a^i c\left(\frac{n}{b^i}\right)^d\\ &=cn^d\left(\frac{a}{b^d}\right)^i. \end{aligned}

比值

\rho=\frac{a}{b^d}

说明代价从一层到下一层怎样变化。

根部占优： $\rho<1$

若 $a<b^d$ ，层代价按等比数列缩小，顶部几层占主导，因此

T(n)\in\Theta(n^d).

例如：

T(n)=2T(n/2)+n^2.

这里 $a=2$ 、 $b=2$ 、 $d=2$ ，所以 $\rho=2/4=1/2$ 。

逐层平衡： $\rho=1$

若 $a=b^d$ ，每个内部层具有相同的渐近代价。再乘以层数可得

T(n)\in\Theta(n^d\log n).

归并排序中 $a=2$ 、 $b=2$ 、 $d=1$ ，所以 $\rho=1$ 。

叶子占优： $\rho>1$

若 $a>b^d$ ，层代价按等比数列增长，树的底部占主导，而叶子数量决定最终阶数：

T(n)\in\Theta\!\left(n^{\log_b a}\right).

对

T(n)=4T(n/2)+n,

有 $\rho=4/2=2$ 。叶子数量为

n^{\log_2 4}=n^2,

所以 $T(n)\in\Theta(n^2)$ 。

简化版主定理

上面三种比较构成了一个实用的主定理版本。对

T(n)=aT(n/b)+\Theta(n^d),

其中 $a\ge1$ 、 $b>1$ 、 $d\ge0$ ，并满足常规正则条件，比较 $d$ 与 $\log_b a$ ：

T(n)= \begin{cases} \Theta\!\left(n^{\log_b a}\right), & d<\log_b a,\\[4pt] \Theta(n^d\log n), & d=\log_b a,\\[4pt] \Theta(n^d), & d>\log_b a. \end{cases}

这个版本覆盖多项式形式的合并代价。更一般的主定理还可以处理对数因子，并需要更精确的条件；本节暂时不需要这些扩展。

有纪律的使用步骤

面对一个新递推式：

1. 从算法中识别 $a$ 、 $b$ 和 $f(n)$ ； 2. 写明基础情况； 3. 若 $f(n)=\Theta(n^d)$ ，计算 $d$ 与 $\log_b a$ ； 4. 选择相应情况； 5. 用递归树的层代价检查结论。

最后一步很重要。死记某个“第几种情况”很容易出错，而递归树能解释答案为什么具有该增长率。

主定理不能直接处理哪些递推式

上面展示的形式不能直接处理所有递推式。例如，

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

的子问题规模是 $n-1$ ，而不是 $n/b$ ；又如

T(n)=T(n/3)+T(2n/3)+n

的两个子问题规模并不相等。

这些递推式仍然可以用展开、代入或更一般的递归树方法分析。定理是带有前提条件的工具，不能只凭外观套公式。

正在加载交互实验...

正在加载概念检查...

正在加载本节练习...

注意

不能只根据递归调用数量判断分治算法的界。必须统计每层工作量、层数，并把叶子代价包括进来。

本章衔接

第 8 章将转向整数。整除与素因数分解会为模运算和密码学提供结构，而递归推理也会再次出现在欧几里得算法中。

7.3 分治递推与递归树

7.3 分治递推与递归树

从算法写出代价递推式

例子：二分查找只产生一个更小调用

递归树展示每一次调用

例子：归并排序每个内部层的工作量相等

递归树代价的三种分布方式

根部占优：ρ<1\rho<1ρ<1

逐层平衡：ρ=1\rho=1ρ=1

叶子占优：ρ>1\rho>1ρ>1

简化版主定理

有纪律的使用步骤

主定理不能直接处理哪些递推式

本章衔接

7.3 分治递推与递归树

7.3 分治递推与递归树

从算法写出代价递推式

例子：二分查找只产生一个更小调用

递归树展示每一次调用

例子：归并排序每个内部层的工作量相等

递归树代价的三种分布方式

根部占优：ρ<1\rho<1ρ<1

逐层平衡：ρ=1\rho=1ρ=1

叶子占优：ρ>1\rho>1ρ>1

简化版主定理

有纪律的使用步骤

主定理不能直接处理哪些递推式

本章衔接

根部占优： $\rho<1$

逐层平衡： $\rho=1$

叶子占优： $\rho>1$

根部占优： $\rho<1$

逐层平衡： $\rho=1$

叶子占优： $\rho>1$