Algorinote_2_主定理与 Akra-Bazzi 定理

Algorinote_10_主定理与 Akra-Bazzi 定理

主定理 Master theorem

对于形如 $T(n)=aT(\frac{n}{b})+f(n)$ 的递归式，其中：

• n 是问题规模大小；
• a 是原问题的子问题个数；
• n/b 是每个子问题的大小，这里假设每个子问题有相同的规模大小；
• f(n) 是将原问题分解成子问题和将子问题的解合并成原问题的解的时间。

令 d 是 f(n) 中 n 的最高幂次，$f(n)=\Theta (n^d)$。

拿 $f(n)$ 与 $n^{{\log }_{b}a}$ 的增长速度进行对比，原理上是在每层的单个子问题的治理时间 $a^{layer}$，与子问题的数量之间作权衡 $b^{d\ast layer}$（具体证明可以看看下文），实际是比较 $d-{\log }_{b}a$ 或 $a-b^d$ 。于是有：

• 如果后者更大，则 $T(n)=\Theta (n^{lo{g}_{b}a})$
• 如果二者相等，则 $T(n)=\Theta (n^{{\log }_{b}a}{\log }^{k+1}n)=\Theta (n^d\log n)$
• 如果前者更大，则 $T(n)=\Theta (n^d)$
  • 注意还需要对充分大的 n，存在 c < 1 使 $af(\frac{n}{b})\le cf(n)$

其中第二点中，因为在对 $f(n)$ 的分析时得到的通常都是多项式 $n^d$ 形式，即原文所提到的 ${\log }^{k}n$ 形式一般都是 k=0，所以我们把第二点化简成 $iff(n)=\Theta (n^{{\log }_{b}a})$，也就是 $d={\log }_{b}a$

应用

认真理解一下 $T(n)=aT(\frac{n}{b})+f(n)$，a 代表当前层的分支数，f(n) 代表分支前的耗时，也就是本层用时，b 代表分解时对当前问题的切分程度，也即子问题与母问题的比例。

所以对于我们熟悉的快速排序，有 $T(n)=2T(\frac{n}{2})+O(n)$，所以 $d=1={\log }_{2}2=1$，$T(n)=\Theta (n\log n)$

证明

根据对递归式的理解，第$i$层有$a^i$个子问题，每个子问题的大小是 $n/b^i$

所以这一层的用时是 $a^i\cdot O((\frac{n}{b^i}{)}^d)=O(n^d)\cdot (\frac{a}{b^d}{)}^i$

把每层用时累加起来就是 KaTeX parse error: Expected group after '_' at position 5: \sum_̲\limits{i=0}^{\…，可以看出是一个等比数列，公比 $q=\frac{a}{b^d}$ ，考虑对 q 进行分类讨论（省略化简过程）

• q > 1，即$d<{\log }_{b}a$，最后一项占主导，$S=O(O(n^d)(\frac{a}{b^d}{)}^{{\log }_{b}a})=O(n^{{\log }_{b}a})$
• q = 1，全都一样大，求和 $S=(1+{\log }_{b}a)O(n^d)=O(n^d\log n)$
• q < 1，即$d>{\log }_{b}a$，第一项占主导，$S=O(O(n^d)\cdot 1)=O(n^d)$
  • 此时当 f(n) 不是 n 的简单次幂形式（含有 log）时，还需要考虑 $af(\frac{n}{b})\le cf(n)$ 来保证序列增长级递减

Akra-Bazzi 定理

考虑形如 $T(x)=\sum _{i=1}^k{a}_{i}T(b_{i}x+h_i(x))+f(x),forx\ge x_0$ 的递归式（T的转移可以有更多部分），其中：

• $a_i>0, 0<b_i<1 $
• $|g(x)|\in O(x^c)，其中c是常数$
• $|h_i(x)|\in O(\frac{x}{{\log }^{2}x})$

则有 $T(x)=\Theta (x^p+x^p\cdot {\int }_1^x\frac{f(u)}{u^{p+1}}du)$，其中$\sum _{i=1}^k{a}_i{b}_i^p=1$

应用

例题1$T(n)=\frac{7}{4}T(\frac{1}{2}n)+T(\frac{3}{4}n)+n^2$

​ 先找 p：$\frac{7}{4}(\frac{1}{2}{)}^p+(\frac{3}{4}{)}^p=1$，解得 p=2

​ 所以 $T(x)=\Theta (x^2(1+{\int }_1^x\frac{u^2}{u^3}du))=\Theta (x^2(1+\log x))=\Theta (x^2\log x)$

例题2$T(n)=\frac{1}{4}T(\frac{3}{4}n)+\frac{3}{4}T(\frac{1}{4}n)+1$

​ 显然 p=0，$T(x)=\Theta (1+{\int }_1^x\frac{1}{u}du)=\Theta (\log x)$

Ref

https://zhuanlan.zhihu.com/p/100531135

https://my.oschina.net/u/4324616/blog/4778589