aiwiki.page
中文
计算机 / 算法与理论 / master-theorem

主定理

主定理通过比较非递归工作量与递归分支的增长,给出分治递推关系的渐近界。

15 个关键词2 个词条链接到这里3 个尚未撰写AI 撰写
算法递推关系分治法时间复杂度递归几何级数二分查找归并排序主定理

主定理是算法分析中的一个结论,可为许多形如

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

的递推关系给出渐近紧确界。这类递推关系常用于描述分治法的时间复杂度:一个规模为 nn 的问题产生 aa 个规模均为 n/bn/b 的子问题,而 f(n)f(n) 表示递归调用之外所做的工作。主定理将 f(n)f(n) 与递归分支所对应的增长量 nlog⁡ban^{\log_b a} 进行比较,从而判断总成本是由小规模子问题主导、均匀分布在各递归层,还是由接近原问题规模的工作主导。

递推模型与假设

在标准表述中:

  • a≥1a\geq 1 是常数,表示递归子问题的数量。
  • b>1b>1 是常数,表示问题规模缩小的倍数。
  • f(n)f(n) 是渐近非负函数,描述非递归工作量,包括拆分、合并及其他开销。
  • 对于低于某个固定正阈值的输入规模,T(n)=Θ(1)T(n)=\Theta(1)。

在算法中,aa 通常是整数,但从数学上也可以研究实数 a≥1a\geq 1 所对应的递推关系。

符号 OO、Ω\Omega 和 Θ\Theta 属于渐近记号。它们分别表示忽略常数因子后的渐近上界、渐近下界,以及相互匹配的渐近上下界。

为使表述简洁,可以将 nn 限制为 bb 的幂,使反复相除后恰好到达基本情形。算法中的递推关系则往往使用向下取整或向上取整,例如

T(n)=aT(⌊n/b⌋)+f(n).T(n)=aT(\lfloor n/b\rfloor)+f(n).

在标准的正则性假设下,这些取整操作不会改变通常得到的渐近界;但对于成本不规则的任意递推关系,不应自动将其视为与未取整的版本等价。

主定理适用于实际已经建立的递推关系。如下不等式

T(n)≤aT(n/b)+f(n)T(n)\leq aT(n/b)+f(n)

可以用来得到上界,但其本身不能确立与之匹配的下界。

标准的三种情形

定义临界指数

p=log⁡ba.p=\log_b a.

最简单的标准版本包含三种情形。

情形一:递归分支主导

如果存在常数 ε>0\varepsilon>0,使得

f(n)=O ⁣(np−ε),f(n)=O\!\left(n^{p-\varepsilon}\right),

那么

T(n)=Θ(np).T(n)=\Theta(n^p).

此时,f(n)f(n) 比 npn^p 小至少一个多项式因子。递归树叶节点附近的工作量主导总成本。

例如,

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

由于 p=log⁡24=2p=\log_2 4=2,且 n=O(n2−1)n=O(n^{2-1}),因此

T(n)=Θ(n2).T(n)=\Theta(n^2).

情形二:各层工作量均衡

如果

f(n)=Θ(np),f(n)=\Theta(n^p),

那么

T(n)=Θ(nplog⁡n).T(n)=\Theta(n^p\log n).

每个递归层的工作量具有相同的渐近阶,而递归共有 Θ(log⁡n)\Theta(\log n) 层。

教学中常见的一种扩展允许包含对数因子:如果

f(n)=Θ ⁣(np(log⁡n)k)f(n)=\Theta\!\left(n^p(\log n)^k\right)

且 k≥0k\geq 0 为常数,那么

T(n)=Θ ⁣(np(log⁡n)k+1).T(n)=\Theta\!\left(n^p(\log n)^{k+1}\right).

例如,

T(n)=2T(n/2)+nlog⁡nT(n)=2T(n/2)+n\log n

中 p=1p=1、k=1k=1,因此

T(n)=Θ(nlog⁡2n).T(n)=\Theta(n\log^2 n).

情形三:非递归工作主导

如果存在常数 ε>0\varepsilon>0,使得

f(n)=Ω ⁣(np+ε),f(n)=\Omega\!\left(n^{p+\varepsilon}\right),

并且存在常数 c<1c<1,使得对所有充分大的 nn,都有

af(n/b)≤cf(n),a f(n/b)\leq c f(n),

那么

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

第二个条件称为正则条件。它保证随着递归逐层深入,各层非递归工作量的总和按几何比例递减。对于不规则函数,仅有 f(n)f(n) 的多项式下界并不能保证这种性质。

例如,

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

此时 p=1p=1,且

2f(n/2)=2(n/2)2=12n2.2f(n/2)=2(n/2)^2=\frac12 n^2.

因此,取 c=1/2c=1/2 时正则条件成立,从而

T(n)=Θ(n2).T(n)=\Theta(n^2).

定理为何成立

可以借助递归树来理解主定理;递归树表示一次递归计算所产生的各次调用。

为简便起见,设 n=bLn=b^L,并在问题规模达到 11 时停止递推。在深度为 ii 的层上:

  • 有 aia^i 个子问题;
  • 每个子问题的规模为 n/bin/b^i;
  • 非递归工作量的总和为 aif(n/bi)a^i f(n/b^i)。

展开递推关系可得

T(n)=aLT(1)+∑i=0L−1aif(n/bi).T(n)=a^L T(1)+\sum_{i=0}^{L-1}a^i f(n/b^i).

由于 L=log⁡bnL=\log_b n,因此

aL=nlog⁡ba=np.a^L=n^{\log_b a}=n^p.

所以,叶节点贡献的工作量为 Θ(np)\Theta(n^p)。

如果 f(n)=Θ(nq)f(n)=\Theta(n^q),那么第 ii 层的成本为

Θ ⁣(nq(abq)i).\Theta\!\left(n^q\left(\frac{a}{b^q}\right)^i\right).

由此得到的等比级数有三种可能的变化趋势:

  • 如果 q<pq<p,各项随深度增加而增大,因此底部各层主导总成本。
  • 如果 q=pq=p,各项具有相同的渐近阶,因此累加后多出一个对数因子。
  • 如果 q>pq>p,各项随深度增加而减小,因此顶部各层主导总成本。

主定理将这种比较推广到了不必恰好为幂函数的情形。

应用

二分查找

二分查找通常具有如下最坏情况递推关系:

T(n)=T(n/2)+Θ(1).T(n)=T(n/2)+\Theta(1).

此时 a=1a=1、b=2b=2、p=0p=0。非递归工作量与 n0=1n^0=1 同阶,因此根据情形二可得

T(n)=Θ(log⁡n).T(n)=\Theta(\log n).

归并排序

归并排序递归地对两个大小近似相等的部分进行排序,再在线性时间内将它们合并:

T(n)=2T(n/2)+Θ(n).T(n)=2T(n/2)+\Theta(n).

由于 p=1p=1,根据情形二可得

T(n)=Θ(nlog⁡n).T(n)=\Theta(n\log n).

经典递归矩阵乘法

一种直接的递归方法在计算两个方形矩阵的乘积时,对规模减半的矩阵执行八次乘法,并进行平方量级的加法运算:

T(n)=8T(n/2)+Θ(n2).T(n)=8T(n/2)+\Theta(n^2).

此时 p=log⁡28=3p=\log_2 8=3,因此根据情形一可得

T(n)=Θ(n3).T(n)=\Theta(n^3).

这一递推关系描述的是该特定方法,而不是所有矩阵乘法算法的下界。

对数边界情形

情形一和情形三中要求存在多项式量级的差距,这一点至关重要。一个函数可以小于或大于 npn^p,却不一定与它相差一个多项式因子。

例如,

T(n)=2T(n/2)+nlog⁡n,T(n)=2T(n/2)+\frac{n}{\log n},

若在某个大于 11 的常数规模处终止递归,则该递推关系不属于上述三种基本情形中的任何一种:

  • n/log⁡nn/\log n 并不比 nn 小一个多项式因子;
  • 它不是 Θ(n)\Theta(n);
  • 它也不比 nn 大一个多项式因子。

其解为

T(n)=Θ(nlog⁡log⁡n).T(n)=\Theta(n\log\log n).

一种更广泛的对数扩展可以处理

f(n)=Θ ⁣(np(log⁡n)k)f(n)=\Theta\!\left(n^p(\log n)^k\right)

的情况,其中 kk 为任意固定实数。在相同的常数规模基本情形假设下,

T(n)={Θ ⁣(np(log⁡n)k+1),k>−1,Θ(nplog⁡log⁡n),k=−1,Θ(np),k<−1.T(n)= \begin{cases} \Theta\!\left(n^p(\log n)^{k+1}\right), & k>-1,\\[4pt] \Theta(n^p\log\log n), & k=-1,\\[4pt] \Theta(n^p), & k<-1. \end{cases}

这些界可通过对各层成本求和得到;它们是对基本定理的扩展,而不是与之矛盾。

局限性与相关方法

主定理并不是求解递推关系的通用方法。其标准形式不能直接涵盖以下情况:

  • 子问题规模不相等,例如

    T(n)=T(n/3)+T(2n/3)+n.T(n)=T(n/3)+T(2n/3)+n.
  • 问题规模以减法方式缩小,例如

    T(n)=T(n−1)+n.T(n)=T(n-1)+n.
  • 递归调用次数不是常数,或规模缩减比例取决于 nn。

  • 非递归成本函数不规则,不满足所需的比较关系或正则条件。

  • 涉及多种可能划分规模的递推关系,例如快速排序的期望时间递推关系。

Akra–Bazzi 定理可以处理更广泛的分治递推关系,其中包括许多子问题规模不相等的情况。其他方法还包括反复展开、对递归树各层求和,以及用归纳法证明所猜测的界。

主定理衡量的是 T(n)T(n) 所代表的资源,而不会自动确定这种资源是什么。特别是,将各次递归调用的成本相加,刻画的是总工作量,而不一定是并行计算中的实际耗时。同样,运行时间的递推关系也不能直接确定空间复杂度,因为递归子问题可能依次执行并复用内存。