Master Theorem

Master Theorem

分治策略的递推式通常形如 $T(n)=a\cdot T\left(\frac{n}{b}\right)+O(g(n))$，表示原问题被分为 $a$ 个 $b$ 规模的子问题，原问题自身需要 $g(n)$ 时间。

• 若 $g(n)=\Omega (n^{{\log }_{b}a+ϵ})$，则 $T(n)=\Theta (g(n))$
• 若 $g(n)=O(n^{{\log }_{b}a-ϵ})$，则 $T(n)=\Theta (n^{{\log }_{b}a})$
• 若 $g(n)=\Theta (n^{{\log }_{b}a}\cdot {\log }^{k}n),k\ge 0$，则 $T(n)=\Theta (g(n)\cdot \log n)$ 直观理解： 构造了一颗 $a$ 叉树，每层问题规模减少为 $\frac{1}{b}$ 倍，则树共 ${\log }_{b}n$ 层，遍历这棵树需 $O(a^{{\log }_{b}n})=O(n^{{\log }_{b}a})$ 时间 更一般地，有 Akra-Bazzi Theorem

Akra-Bazzi Theorem

可以理解为泛化的主定理。

参数 $p$ 可类比为 ${\log }_{b}a$

• $g(n)$ 增长慢于 $n^p$，$T(n)=\Theta (n^p)$
• $g(n)$ 增长等于 $n^p$，$T(n)=\Theta (n^p\log n)$
• $g(n)$ 增长快于 $n^p$，$T(n)=\Theta (g(n))$

Example

$$T(n)=\sum _{k=1}^{9}T(k\cdot n)/2025+\sqrt[2025]{\prod _{k=3}^{12}{n}^{k^3}}$$

运用自然数立方求和公式，

$$\sum _{i=1}^9{a}_i{b}_i^p=\frac{1}{2025}\sum _{k=1}^9{k}^p=1$$

取 $p=3$，发现成立

$$\ln g(n)=\frac{1}{2025}\sum _{k=3}^{12}{k}^3\cdot \ln n=\frac{1}{2025}(78^2-9)\ln n=3\ln n$$

因此 $O(g(n))=n^3$ 因此 $T(n)=O(n^3\log n)$

例：大数乘法