算法导论基础-几种递归式解法总结

1 代换法

求解步骤：
1.猜测解的形式
2.用数学归纳法求出解中的常数，并证明解是正确的。

---

2 递归树法

---

3 主方法(常用)

递归通式：T(n)=aT(n/b)+f(n)

其中f(n)是非递归的,$a\ge1$,$b>1$
f(n)渐进趋正（对于足够大的n，$f(n)\ge0$)

考虑 f(n) 与 $n^{\log_{b}{a}}$,

情况一：f(n)<$n^{\log_{b}{a}}$–>O($n^{\log_{b}{a}-\xi}$)($\xi>0$)
$\therefore$ T(n)=$\theta$($n^{\log_{b}{a}}$)。

情况二：f(n)=$n^{\log_{b}{a}}$–>$\theta$($n^{\log_{b}{a}}\cdot (\lg_{}{n})^{k}$),$k\ge0$
$\therefore$ T(n)=$\theta$($n^{\log_{b}{a}}\cdot (\lg_{}{n})^{k}$)

情况三：f(n)>$n^{\log_{b}{a}}$–>O($n^{\log_{b}{a}-\xi}$)($\xi>0$),
$\because af(n/b)\le (1-\xi ^{‘} )f(n)$
$\therefore T(n)=\theta (f(n))$

---