递推式求解：展开、递归树与主定理

Views: --

递归算法的时间复杂度通常写成“子问题成本 + 当前层成本”。求解递推式的关键不是背答案，而是看清每层有多少子问题、每个多大、当前层做多少额外工作。

1. 直接展开

例如

T(n)=T(n−1)+n,T(1)=Θ(1).T(n)=T(n-1)+n, \qquad T(1)=\Theta(1).

连续展开：

T(n)=T(1)+2+3+⋯+n=Θ(n2).T(n)=T(1)+2+3+\cdots+n=\Theta(n^2).

再如

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

每次规模减半，展开 log⁡2n\log_2n 次后到达 1，所以 T(n)=Θ(log⁡n)T(n)=\Theta(\log n)。

直接展开适合单分支递归和容易求和的递推式。

2. 代入法

代入法本质是“先猜答案，再用归纳法证明”。例如猜

T(n)≤cnlog⁡n.T(n)\le cn\log n.

对

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

代入归纳假设：

T(n)≤2cn2log⁡n2+n=cnlog⁡n−cn+n.T(n) \le2c\frac n2\log\frac n2+n =cn\log n-cn+n.

当 c≥1c\ge1 时不超过 cnlog⁡ncn\log n，上界成立。再证明同阶下界即可得到 Θ(nlog⁡n)\Theta(n\log n)。

若差一个低阶项导致归纳闭合不了，可加强猜想，例如从 cncn 改成 cn−dcn-d。这不是作弊，而是在给归纳留出“余量”。

3. 递归树

考虑

T(n)=3T(n/4)+cn2.T(n)=3T(n/4)+cn^2.

第 ii 层有 3i3^i 个规模 n/4in/4^i 的子问题，因此该层非递归成本为

3ic(n4i)2=cn2(316)i.3^i c\left(\frac{n}{4^i}\right)^2 =cn^2\left(\frac{3}{16}\right)^i.

这是收敛几何级数，根层工作占主导，所以 T(n)=Θ(n2)T(n)=\Theta(n^2)。

递归树最直观的价值是判断：

  • 每层成本在下降：根层主导；
  • 每层成本相同：层数带来一个 log⁡n\log n；
  • 每层成本在上升：叶子层主导。

4. 主定理

对

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

递归树有 log⁡bn\log_b n 层，叶子数约为

alog⁡bn=nlog⁡ba.a^{\log_b n}=n^{\log_ba}.

因此把 f(n)f(n) 与 nlog⁡ban^{\log_ba} 比较。

4.1 子问题主导

若存在 ε>0\varepsilon>0，使

f(n)=O(nlog⁡ba−ε),f(n)=O\left(n^{\log_ba-\varepsilon}\right),

则叶子贡献更大：

T(n)=Θ(nlog⁡ba).T(n)=\Theta\left(n^{\log_ba}\right).

4.2 各层同阶

若

f(n)=Θ(nlog⁡balog⁡kn),f(n)=\Theta\left(n^{\log_ba}\log^kn\right),

则

T(n)=Θ(nlog⁡balog⁡k+1n).T(n)=\Theta\left(n^{\log_ba}\log^{k+1}n\right).

最常见的 k=0k=0 情形就是多乘一个 log⁡n\log n。

4.3 根层主导

若存在 ε>0\varepsilon>0，使

f(n)=Ω(nlog⁡ba+ε),f(n)=\Omega\left(n^{\log_ba+\varepsilon}\right),

并满足正则条件

af(n/b)≤cf(n),c<1,af(n/b)\le cf(n),\qquad c<1,

则

T(n)=Θ(f(n)).T(n)=\Theta(f(n)).

正则条件保证 ff 不会剧烈波动，使根层确实占主导。

5. 典型例题

递推式比较结果
2T(n/2)+n2T(n/2)+nf(n)=nlog⁡22f(n)=n^{\log_2 2}Θ(nlog⁡n)\Theta(n\log n)
4T(n/2)+n4T(n/2)+n叶子规模 n2n^2 更大Θ(n2)\Theta(n^2)
T(n/2)+nT(n/2)+n根层工作更大Θ(n)\Theta(n)
2T(n/2)+nlog⁡n2T(n/2)+n\log n临界项多一个 log⁡n\log nΘ(nlog⁡2n)\Theta(n\log^2n)
7T(n/2)+n27T(n/2)+n^2nlog⁡27n^{\log_2 7} 更大Θ(nlog⁡27)\Theta(n^{\log_2 7})

6. 主定理不能乱套

以下递推式不能直接套标准主定理：

  • T(n)=T(n−1)+nT(n)=T(n-1)+n：子问题不是 n/bn/b；
  • T(n)=T(n/2)+T(n/4)+nT(n)=T(n/2)+T(n/4)+n：子问题规模不同；
  • T(n)=2nT(n/2)+nT(n)=2^nT(n/2)+n：aa 不是常数；
  • T(n)=2T(n/2)+nlog⁡log⁡nT(n)=2T(n/2)+n\log\log n：不一定落入最基础三种模板。

这时可用展开、递归树、Akra-Bazzi 定理或上下界夹逼。

7. 非等分子问题的递归树

例如

T(n)=T(n/2)+T(n/4)+T(n/8)+n.T(n)=T(n/2)+T(n/4)+T(n/8)+n.

下一层所有子问题规模之和是 7n/87n/8，所以每层总代价按 7/87/8 递减：

n+78n+(78)2n+⋯=Θ(n).n+\frac78n+\left(\frac78\right)^2n+\cdots=\Theta(n).

无需先求出叶子数，也能看出 T(n)=Θ(n)T(n)=\Theta(n)。

8. 写答案的规范顺序

  1. 写清基础情形；
  2. 说明采用的方法；
  3. 展示每层代价或主定理参数；
  4. 求和；
  5. 用 Θ\Theta 给出紧确结果。

只写“由主定理得”而不列 a,b,f(n)a,b,f(n)，考试时很容易因套错情形丢分。

评论