主定理(master定理)

主定理

1.简介

主定理用于解决形如以下形式的递归算法的时间复杂度：
$$T(n)=aT(n/b)+f(n)$$

$a$为子问题个数，$b$为子问题的规模

其中需满足 $a\ge 1,b>1$

则答案有三种情况：

1. 若函数 $n^{lo{g}_{b}a}$ 更大，则 $T(n)=O(n^{lo{g}_{b}a})$;
2. 若函数 $f(n)$ 更大，且满足 $af(n/b)\le cf(n)$ ,则 $T(n)=O(f(n))$ ;
3. 若两函数相等，则 $T(n)=O(n^{lo{g}_{b}a}lo{g}^{k+1}n)$

简化一下，即为比较 $f(n)$ 和 $O(n^{lo{g}_{b}a})$ 的大小，取大的，若是相同就加上 $logn$ 的复杂度。

一些例子

二分查找(Bintary Search)

$T(n)=T(n/2)+O(1)$
分析：$a=1,b=2,$基准函数 $O(n^{lo{g}_{b}a})=O(n^0)=O(1)$
适用于Case3，即$T(n)=O(logn)$

二叉树遍历(Binary tree traversal)

$T(n)=2T(\frac{n}{2})+O(1)$

分析： $a=b=2,f(n)=O(1)$ ,基准函数 $O(n^{lo{g}_{2}2})=\Theta (n)$ ，适用于Case1,所以 $T(n)=O(n^{lo{g}_{b}a})=O(n)$

一个随便出的递推式

$T(n)=3T(n/4)+O(n)$
$O(n^{{\log }_{b}a})=O(n^{{\log }_{4}3})=O(1)<O(n)$
所以复杂度为 $O(n)$
​