（转）如何分析分治型算法性能

算法分析 排序算法

---

主定理 Master Method

假设有递推关系式

$T(n) = a \; T\left(\frac{n}{b}\right) + f(n)$，其中 $a \geq 1 \mbox{, } b > 1$
其中，$n$为问题规模，$a$为递推的子问题数量，$n/b$为每个子问题的规模（假设每个子问题的规模基本一样），$f(n)$为递推以外进行的计算工作:包含问题分解和子问题解合并的代价

情形一

如果存在常数$\epsilon > 0$，有$f(n) = O\left( n^{\log_b (a) - \epsilon} \right)$，并且是多项式的小于
那么

$$T(n) = \Theta\left( n^{\log_b a} \right)$$

情形二

如果存在常数$k ≥ 0$，有$f(n) = \Theta\left( n^{\log_b a} \log^{k} n \right)$, 那么

$$T(n) = \Theta\left( n^{\log_b a} \log^{k+1} n \right)$$

情形三

如果存在常数$\epsilon > 0$，有$f(n) = \Omega\left( n^{\log_b (a) + \epsilon} \right)$，并且是多项式的大于, 同时存在常数$c < 1$以及充分大的$n$，满足$a f\left( \frac{n}{b} \right) \le c f(n)$, 即保证下一层比上一层小， 那么

$$T\left(n \right) = \Theta \left(f \left(n \right) \right)$$

常用算法中的应用

---

------算法 ----------- 递推关系式-------

• 折半搜索-- $T(n) = T\left(\frac{n}{2}\right) + \Theta(1)--运算时间: \Theta(\log(n)) -- 情形二（k = 0）$
• 二叉树遍历-- $T(n) = 2 T\left(\frac{n}{2}\right) + \Theta(1)-- 运算时间: \Theta(n) --情形一$

• 归并排序-- $T(n) = 2 T\left(\frac{n}{2}\right) + \Theta(n)-- 运算时间: \Theta(n\log(n))--情形二（k = 0）$
  sol: $f(n)=\theta(n)=\theta( n^{log_{2}{2}}log^0{n}) ,T(n)=n^{log_22}log^1n=nlog(n)$

  参考资料

  1 主定理-维基百科 http://zh.wikipedia.org/wiki/%E4%B8%BB%E5%AE%9A%E7%90%86
  [2]