算法与数据结构 · 第 6 课
不均匀分治递归:Master 定理不适用时怎么办?
2026 年 10 月 25 日|第 1 周第 6 课|预计 18 分钟
核心问题: 归并排序若不是平分成两个 (n/2) 子问题,而是分成 (n/3) 与 (2n/3),还会是 (O(n\log n)) 吗?如果每一层的合并成本从 (n) 变成 (n/\log n),复杂度又会发生什么变化?
学习目标与前提
学完应能够:(1)从伪代码准确写出不均匀递归;(2)用递归树的规模守恒证明上下界;(3)理解 Akra–Bazzi 指数 (p) 与积分项的含义;(4)区分真正的双分支递归与上一课 BFPRT / Quickselect 中的“只进入部分子问题”。
假设比较、移动一个元素的成本为 (O(1)),输入规模是正整数;(\log) 表示任意固定底数大于 1 的对数,渐近阶与底数无关。
一、动机:两个递归分支为什么不能简单当作两个 n/2?
标准归并排序通常满足
[ T(n)=2T(n/2)+\Theta(n), ]
直接用 Master 定理得到 (\Theta(n\log n))。
现在考虑一种不均匀归并排序:每次将数组切成前 (k=\max(1,\lfloor n/3\rfloor)) 个元素和剩下 (n-k) 个元素,各自排序后线性归并。若只关心排序,正确性不依赖两边必须等长;如果再顺手数出逆序对,就得到一个很好的算法案例。
逆序对定义为 (i<j) 且 (A_i>A_j) 的数对,相等元素不算。下面的伪代码同时返回有序数组和逆序对数量。
SortCount(A):
n = |A|
if n <= 1: return (A, 0)
k = max(1, floor(n/3))
(L, cL) = SortCount(A[0:k])
(R, cR) = SortCount(A[k:n])
(M, cCross) = MergeAndCount(L, R)
return (M, cL + cR + cCross)
MergeAndCount(L, R):
i = j = cross = 0
M = []
while i < |L| and j < |R|:
if L[i] <= R[j]:
append M, L[i]; i++
else:
append M, R[j]
cross += |L| - i
j++
append remaining elements
return (M, cross)
| 归并阶段的核心不变量:L、R 各自有序;每当 R[j] < L[i] 时,L[i],L[i+1],… 全都大于 R[j],恰好新增 ( | L | -i) 个跨区间逆序对。相等时先取左边元素,避免把相等元素误算为逆序。递归归纳可证:两个子数组内部逆序对由递归正确计数,所有跨区间逆序对由归并一次且仅一次计数,因此输出排序正确且计数准确。 |
例如 ([4,1,3,2,6,5]) 分成 ([4,1]) 与 ([3,2,6,5]):左侧内部 1 个,右侧内部 2 个,跨区间是 4 大于 2、3 的 2 个,总计 5 个。
二、从伪代码写出递归与执行 Trace
设 (T(1)=1),每个长度为 (n\ge2) 的非叶节点花费 (n) 个抽象工作单位,令 (k=\max(1,\lfloor n/3\rfloor)):
[ \boxed{T(n)=T(k)+T(n-k)+n.}\tag{1} ]
真实算法的归并工作为 (\Theta(n)),式 (1) 选取具体常数是为了让手算结果可重复。对 (n\ge3),两支规模约为 (n/3) 和 (2n/3)。特别设置 (\max(1,\cdot)) 是为了避免 (n=2) 时分出空数组、产生不缩小的递归。
flowchart TD
A["12,当前工作 12"] --> B["4,当前工作 4"]
A --> C["8,当前工作 8"]
B --> D["1"]
B --> E["3"]
C --> F["2"]
C --> G["6"]
E --> H["1 + 2"]
F --> I["1 + 1"]
G --> J["2 + 4"]
| 子问题 n | 分裂 | T(n) |
|---|---|---|
| 1 | 基例 | 1 |
| 2 | 1+1 | 4 |
| 3 | 1+2 | 8 |
| 4 | 1+3 | 13 |
| 6 | 2+4 | 23 |
| 8 | 2+6 | 35 |
| 12 | 4+8 | 60 |
检查 (T(12)):根节点贡献 12,再加 (T(4)=13) 与 (T(8)=35)。这是一棵左右深度不同的递归树,但不意味着总复杂度一定比均匀归并差。
三、严格证明 (\Theta(n\log n)):不是“每层都是 n”那么简单
这里先不引用 Akra–Bazzi,直接证明式 (1) 的阶。
上界。 对 (n\ge3),较大的孩子至多为 (\lceil2n/3\rceil)。对于充分大的 (n),可用某个严格小于 1 的常数 (\rho)(例如 (3/4))上界每步剩余规模比;有限的小规模只增加常数层。因此递归树高度 (O(\log n))。同一层所有节点代表互不重叠的数组段,长度之和不超过原始的 (n);节点代价与其长度成正比。因此每层工作最多 (O(n)),有
[ T(n)=O(n\log n). ]
下界。 只看前 (h=\lfloor\log_3(n/2)\rfloor) 层。任何路径每次都保留至少约三分之一的元素;由于使用整数取整,路径上最小子问题长度也至少为 (\lfloor n/3^h\rfloor)。在这些层中节点仍需继续分裂,并且每层的子数组长度总和等于 n。每层于是贡献 (\Omega(n)),共有 (\Omega(\log n)) 层。因此
[ T(n)=\Omega(n\log n). ]
合并上下界:
[ \boxed{T(n)=\Theta(n\log n).}\tag{2} ]
易错点: 接近树底部时已经有很多短分支提前结束,所以“所有层的总规模都等于 n”不成立;上界只需“至多 n”,下界只数前面尚未结束的足够多层。这是完整证明与口头直觉的差别。
四、Master 定理的边界与 Akra–Bazzi
最熟悉的 Master 形式是
[ T(n)=aT(n/b)+g(n), ]
其中所有 (a) 个子问题规模相同。(T(n/3)+T(2n/3)+g(n)) 不能原样套用这个版本。它不代表无解,只需更一般的工具。
在适当的基例、正则性及取整误差条件下,Akra–Bazzi 处理
[ T(x)=\sum_{i=1}^k a_iT(b_ix+h_i(x))+g(x), ]
其中 (a_i>0)、(0<b_i<1),(g(x)\ge0) 且足够规则(例如导数有多项式上界),(h_i(x)=O(x/\log^2x))。常数取整误差 (O(1)) 满足要求。
第一步:求临界指数 (p):
[ \boxed{\sum_i a_i b_i^p=1.}\tag{3} ]
它的直觉是:每轮所有孩子的规模 (n_i^p) 加起来,与父节点的 (n^p) 同阶。如果每一支在规模 (n) 时贡献约 (n^p),递归展开的这部分“工作量”恰好守恒。
第二步:把额外开销放进积分:
[ \boxed{ T(n)=\Theta\left(n^p\left[1+\int_{2}^{n} \frac{g(u)}{u^{p+1}}\,du\right]\right). }\tag{4} ]
下限改为任意固定常数只影响低阶/常数项;对非负常规 (g) 可如此写。注意这不是无条件适用于任意递归的万能公式。
在两支 (1/3,2/3) 且各出现一次的情况下:
[ (1/3)^p+(2/3)^p=1 \Longrightarrow p=1. ]
于是只剩下积分中 (g(u)) 的差异。
五、三组边界案例:只改每层工作量,结果却不同
| 递归 (T(n)=T(n/3)+T(2n/3)+g(n)) | Akra–Bazzi 积分(忽略常数下限) | 渐近时间 |
|---|---|---|
| (g(n)=\Theta(n)) | (\int du/u=\Theta(\log n)) | (\Theta(n\log n)) |
| (g(n)=\Theta(n/\log(n+2))) | (\int du/[u\log(u+2)]=\Theta(\log\log n)) | (\Theta(n\log\log n)) |
| (g(n)=\Theta(n/\log^2(n+2))) | (\int du/[u\log^2(u+2)]=\Theta(1)) | (\Theta(n)) |
| (g(n)=\Theta(n^2)) | (\int 1\,du=\Theta(n)) | (\Theta(n^2)) |
第二行积分为什么是 (\log\log n)?对大的 (u),(\log(u+2)=\Theta(\log u)),于是
[ \int^{n}\frac{du}{u\log u} =\log\log n+O(1). ]
第三行则对应
[ \int^{n}\frac{du}{u\log^2u} =\text{常数}-\frac1{\log n}, ]
所以积分有界。这两行是常见的“临界对数因子”反例:不能看到“低于线性”就一律回答 (\Theta(n))。
再看 (T(n)=T(n/4)+T(n/2)+n):(p) 满足 (4^{-p}+2^{-p}=1)。令 (y=2^{-p}),得到 (y^2+y=1),故 (p\approx0.694<1)。代入公式,线性的 (g(n)=n) 主导,得到 (T(n)=\Theta(n))。子问题规模比例之和只有 (3/4),无需假装它和 (1/3+2/3=1) 是同一个情形。
六、联系上一课 BFPRT:两个子问题,但仍可线性
上一课 Median of Medians 选择算法的最坏时间满足某个上界
[ T(n)\le T(\lceil n/5\rceil)+T(7n/10+O(1))+cn. ]
注意它虽然也有两个递归调用,却不同于归并:一个递归用于找枢轴,另一个只搜索目标所在的一边。两个子问题比例之和约为
[ 1/5+7/10=9/10<1. ]
尝试强归纳 (T(m)\le Km),就得到
[ T(n)\le0.9Kn+cn+O(K). ]
当 (K) 足够大,且 (n) 大到足以吸收常数误差时,有 (T(n)\le Kn);有限小规模放进基例即可。因此这是最坏 (O(n)) 的选择算法,与随机 Quickselect 的期望 (O(n)) 要区分。
递归定理也有失效边界:例如 (T(n)=T(n-1)+n=\Theta(n^2)),唯一孩子的缩放比例趋近 1,不能把它当作某个固定 (b<1) 的 Akra–Bazzi 项;又如 (g(n)) 剧烈振荡或取负,必须重新检查定理假设。
时间与空间分析
不均匀归并逆序对计数:时间 (\Theta(n\log n));归并缓冲与递归期间的同时存活数组总空间可实现为 (O(n)),递归栈深度 (O(\log n))。如果代码在每个调用中额外永久缓存中间列表,空间可能更大,必须按具体实现计费。BFPRT 的时间结论只是选择算法,不应误当作所有分治算法的时间。
八、四级自测(满分 100 分,首次不公布答案)
Lv1|机制辨析:Master 定理的适用范围(15 分|预计 2 分钟|单选)
题目: 对固定输入规模 n,一个算法递归处理约 n/3 与 2n/3 两个子问题,并在当前层做 Θ(n) 的合并工作。以下哪项判断最严谨?
A. 经典形式 T(n)=aT(n/b)+f(n) 的 Master 定理不能直接原样套用;可以用递归树或合适条件下的 Akra–Bazzi 分析。
B. 因为较大的子问题占 2n/3,递归必然需要 Θ(n²) 时间。
C. 两个子问题的规模不相等,所以分治算法一定不正确。
D. 只要每层合并为 Θ(n),无论产生多少递归子问题,总时间都必然为 Θ(n log n)。
可选提示:先检查标准 Master 定理对子问题个数和缩放比例的格式要求;再想能否从递归树建立界。
Lv2|手算执行 Trace:递归展开(20 分|预计 4 分钟|数值)
题目: 定义 T(1)=1;对于 n≥2,令 k=max(1,⌊n/3⌋),并规定 T(n)=n+T(k)+T(n−k)。计算 T(12) 的精确整数值,并列出必要的子问题结果。
可选提示:先拆分 12,再分别求较小参数;每个内部节点贡献自己的规模数值。
Lv3|边界与反例:Akra–Bazzi 分段判断(25 分|预计 5 分钟|多选)
题目: 以下递归均有足够的常数规模基例,取整误差为 O(1),并假设 Θ 项为常规正且平滑的函数。哪些复杂度判断正确?(多选)
A. T(n)=T(n/3)+T(2n/3)+Θ(n) 的时间为 Θ(n log n)。
B. T(n)=T(n/3)+T(2n/3)+Θ(n/[log(n+2)]²) 的时间为 Θ(n)。
C. T(n)=T(n/4)+T(n/2)+Θ(n) 的时间为 Θ(n log n)。
D. T(n)=T(n/3)+T(2n/3)+Θ(1) 的时间为 Θ(log n)。
可选提示:分别求满足 Σaᵢbᵢᵖ=1 的 p,再检查 ∫g(u)/u^(p+1)du;不要仅凭根节点工作量判断。
Lv4|设计与证明:逆序对、BFPRT 与边界项(40 分|预计 12 分钟|开放题)
题目: A(10 分)设计一个基于非均匀二路分割(k=max(1,⌊n/3⌋))的归并式逆序对计数算法,写伪代码和跨区间计数不变量,解释重复元素处理。B(12 分)证明它满足 T(n)=T(k)+T(n−k)+Θ(n),并分别给出 Θ(n log n) 的严格上界、下界论证。C(10 分)对确定性选择算法给出的上界 T(n)≤T(⌈n/5⌉)+T(⌈7n/10⌉+O(1))+cn,说明为何能归纳证明最坏 O(n),并解释为什么这与本题归并递归不同。D(8 分)在合适的 Akra–Bazzi 正则条件下,求 T(n)=T(n/3)+T(2n/3)+Θ(n/log(n+2)) 的渐近阶,写出关键积分并讨论与额外开销为 Θ(n) 时的差异。
可选提示:先证明递归计数不变量,再用每层规模守恒和递归高度证界;确定性选择要关注子问题规模比例之和。
前三题可客观判分。第四题只按推导过程和评分标准进行自评或由人工/ChatGPT 批改,不能伪称网站自动理解证明。
九、知识小结与下一讲
遇到递归先写清楚调用了几个子问题、规模是多少、额外工作量是什么,再检查能否套用定理。对于非均匀分治,
[ p:\sum_i a_ib_i^p=1,\qquad T(n)=\Theta\left(n^p\left[1+\int_2^n\frac{g(u)}{u^{p+1}}du\right]\right) ]
是实用工具,但需要验证正则条件。递归树的层级规模守恒与精确上下界,能防止把定理用成纯粹的公式记忆。
下一讲:2026 年 10 月 26 日,第 7 课为第一周复盘。 将用同一组综合题串起渐近记号、摊还势函数、排序/选择与递归证明,并检查常见边界错误;之后第二周进入随机化、概率与哈希。