主定理是算法分析中的一个结论,可为许多形如
T(n)=aT(n/b)+f(n).
的递推关系给出渐近紧确界。这类递推关系常用于描述分治法的时间复杂度:一个规模为 n 的问题产生 a 个规模均为 n/b 的子问题,而 f(n) 表示递归调用之外所做的工作。主定理将 f(n) 与递归分支所对应的增长量 nlogba 进行比较,从而判断总成本是由小规模子问题主导、均匀分布在各递归层,还是由接近原问题规模的工作主导。
递推模型与假设
在标准表述中:
- a≥1 是常数,表示递归子问题的数量。
- b>1 是常数,表示问题规模缩小的倍数。
- f(n) 是渐近非负函数,描述非递归工作量,包括拆分、合并及其他开销。
- 对于低于某个固定正阈值的输入规模,T(n)=Θ(1)。
在算法中,a 通常是整数,但从数学上也可以研究实数 a≥1 所对应的递推关系。
符号 O、Ω 和 Θ 属于渐近记号。它们分别表示忽略常数因子后的渐近上界、渐近下界,以及相互匹配的渐近上下界。
为使表述简洁,可以将 n 限制为 b 的幂,使反复相除后恰好到达基本情形。算法中的递推关系则往往使用向下取整或向上取整,例如
T(n)=aT(⌊n/b⌋)+f(n).
在标准的正则性假设下,这些取整操作不会改变通常得到的渐近界;但对于成本不规则的任意递推关系,不应自动将其视为与未取整的版本等价。
主定理适用于实际已经建立的递推关系。如下不等式
T(n)≤aT(n/b)+f(n)
可以用来得到上界,但其本身不能确立与之匹配的下界。
标准的三种情形
定义临界指数
p=logba.
最简单的标准版本包含三种情形。
情形一:递归分支主导
如果存在常数 ε>0,使得
f(n)=O(np−ε),
那么
T(n)=Θ(np).
此时,f(n) 比 np 小至少一个多项式因子。递归树叶节点附近的工作量主导总成本。
例如,
T(n)=4T(n/2)+n.
由于 p=log24=2,且 n=O(n2−1),因此
T(n)=Θ(n2).
情形二:各层工作量均衡
如果
f(n)=Θ(np),
那么
T(n)=Θ(nplogn).
每个递归层的工作量具有相同的渐近阶,而递归共有 Θ(logn) 层。
教学中常见的一种扩展允许包含对数因子:如果
f(n)=Θ(np(logn)k)
且 k≥0 为常数,那么
T(n)=Θ(np(logn)k+1).
例如,
T(n)=2T(n/2)+nlogn
中 p=1、k=1,因此
T(n)=Θ(nlog2n).
情形三:非递归工作主导
如果存在常数 ε>0,使得
f(n)=Ω(np+ε),
并且存在常数 c<1,使得对所有充分大的 n,都有
af(n/b)≤cf(n),
那么
T(n)=Θ(f(n)).
第二个条件称为正则条件。它保证随着递归逐层深入,各层非递归工作量的总和按几何比例递减。对于不规则函数,仅有 f(n) 的多项式下界并不能保证这种性质。
例如,
T(n)=2T(n/2)+n2.
此时 p=1,且
2f(n/2)=2(n/2)2=21n2.
因此,取 c=1/2 时正则条件成立,从而
T(n)=Θ(n2).
定理为何成立
可以借助递归树来理解主定理;递归树表示一次递归计算所产生的各次调用。
为简便起见,设 n=bL,并在问题规模达到 1 时停止递推。在深度为 i 的层上:
- 有 ai 个子问题;
- 每个子问题的规模为 n/bi;
- 非递归工作量的总和为 aif(n/bi)。
展开递推关系可得
T(n)=aLT(1)+i=0∑L−1aif(n/bi).
由于 L=logbn,因此
aL=nlogba=np.
所以,叶节点贡献的工作量为 Θ(np)。
如果 f(n)=Θ(nq),那么第 i 层的成本为
Θ(nq(bqa)i).
由此得到的等比级数有三种可能的变化趋势:
- 如果 q<p,各项随深度增加而增大,因此底部各层主导总成本。
- 如果 q=p,各项具有相同的渐近阶,因此累加后多出一个对数因子。
- 如果 q>p,各项随深度增加而减小,因此顶部各层主导总成本。
主定理将这种比较推广到了不必恰好为幂函数的情形。
应用
二分查找
二分查找通常具有如下最坏情况递推关系:
T(n)=T(n/2)+Θ(1).
此时 a=1、b=2、p=0。非递归工作量与 n0=1 同阶,因此根据情形二可得
T(n)=Θ(logn).
归并排序
归并排序递归地对两个大小近似相等的部分进行排序,再在线性时间内将它们合并:
T(n)=2T(n/2)+Θ(n).
由于 p=1,根据情形二可得
T(n)=Θ(nlogn).
经典递归矩阵乘法
一种直接的递归方法在计算两个方形矩阵的乘积时,对规模减半的矩阵执行八次乘法,并进行平方量级的加法运算:
T(n)=8T(n/2)+Θ(n2).
此时 p=log28=3,因此根据情形一可得
T(n)=Θ(n3).
这一递推关系描述的是该特定方法,而不是所有矩阵乘法算法的下界。
对数边界情形
情形一和情形三中要求存在多项式量级的差距,这一点至关重要。一个函数可以小于或大于 np,却不一定与它相差一个多项式因子。
例如,
T(n)=2T(n/2)+lognn,
若在某个大于 1 的常数规模处终止递归,则该递推关系不属于上述三种基本情形中的任何一种:
- n/logn 并不比 n 小一个多项式因子;
- 它不是 Θ(n);
- 它也不比 n 大一个多项式因子。
其解为
T(n)=Θ(nloglogn).
一种更广泛的对数扩展可以处理
f(n)=Θ(np(logn)k)
的情况,其中 k 为任意固定实数。在相同的常数规模基本情形假设下,
T(n)=⎩⎨⎧Θ(np(logn)k+1),Θ(nploglogn),Θ(np),k>−1,k=−1,k<−1.
这些界可通过对各层成本求和得到;它们是对基本定理的扩展,而不是与之矛盾。
局限性与相关方法
主定理并不是求解递推关系的通用方法。其标准形式不能直接涵盖以下情况:
子问题规模不相等,例如
T(n)=T(n/3)+T(2n/3)+n.
问题规模以减法方式缩小,例如
T(n)=T(n−1)+n.
递归调用次数不是常数,或规模缩减比例取决于 n。
非递归成本函数不规则,不满足所需的比较关系或正则条件。
涉及多种可能划分规模的递推关系,例如快速排序的期望时间递推关系。
Akra–Bazzi 定理可以处理更广泛的分治递推关系,其中包括许多子问题规模不相等的情况。其他方法还包括反复展开、对递归树各层求和,以及用归纳法证明所猜测的界。
主定理衡量的是 T(n) 所代表的资源,而不会自动确定这种资源是什么。特别是,将各次递归调用的成本相加,刻画的是总工作量,而不一定是并行计算中的实际耗时。同样,运行时间的递推关系也不能直接确定空间复杂度,因为递归子问题可能依次执行并复用内存。