主定理 Master Theorem

其实也可以称作：递归算法的复杂度判定定理

基本公式：

$$T(问题规模)=子问题数*T(子问题规模)+额外计算$$
数学上的表现形式如下：
$$T(n)=a*T(n/b)+f(n)$$
直接计为：
$$T(n)=a*T(n/b)+\Theta(n^d)$$

其中$a >= 1$ 并且 $b > 1$是常量，其表示的意义是 n 表示问题的规模，a 表示递归的次数也就是生成的子问题规模数，b 表示每次递归是原来的$1/b$的规模，$f(n)$表示分解和合并所要花费的时间之和。

解法如下：

• 如果 $d<\log_b a$，时间复杂度为$\Theta(n^{\log_b a})$
• 如果 $d=\log_b a$，时间复杂度为$\Theta(n^d*\log_2 n)$
• 如果 $d>\log_b a$，时间复杂度为$\Theta(n^d)$

分治法举例

1. 归并排序（二路）Merge Sort

分成两个子序列，子序列排序，合并两个子序列

$$T(n)=2T(n/2)+\Theta(n)$$
利用主定理公式求解：
$$T(n)=\Theta(n\log_2 n)$$

2. 二分查找

有序序列中，先和序列中点比较，选择结果的位置，然后再从子序列中查找，并迭代这样的过程

$$T(n)=T(n/2)+\Theta(1)$$
套用Master公式，可得：
$$T(n)=\Theta(\log_2 n)$$