主定理的推导 Master theorem

2018-12-08 本文已影响14人荷茗

关于递推问题算法复杂度的的推导。
递推公式： $T(n) = aT(\frac{n}{b})+O(n^{d}), a>0,b>1,d\geq 0$

分三种情况:
$T(n) = \begin{cases} O(n^{d}) & \text{if } d > log_{b}a \\ O(n^{d} logn) & \text{if }d = log_{b}a \\ O(n^{log_{b}a})&\text{if } d < log_{b}a \end{cases}$

由递推公式可得:
$T(n) \leq cn^{d} \sum_{i=0}^{log_{b}n-1}(\frac{a}{b^d})^i$

$\text{let } r= \frac{a}{b^d}$

$\text{If } r > 1,\ T(n) \leq cn^{d} \frac{r^{log_bn} - 1} {r- 1}$

$r^{log_bn} = r^\frac{log_rn}{log_rb} = n ^{\frac{1}{log_rb}} = n ^{\frac{1}{\frac{log_bb}{log_br}}} = n ^{ log_br}$

$cn^{d} \frac{r^{log_bn} - 1} {r- 1} = c \frac{n^{d} (n ^{ log_br} -1)} {r- 1} \leq c \frac{n^{d} n ^{ log_br}} {r- 1} = c \frac{n^{d} n ^{ log_ba-log_bb^d}} {r- 1} = \frac{c n^{log_ba}}{r-1} = O(n^{log_ba})$

$\text{If } r < 1, T(n) = cn^{d} \sum_{i=0}^{log_{b}n-1}(r)^i \leq cn^{d}\sum_{i=0}^{\infty}(r)^i = cn^{d}\cdot \frac{1}{1-r} = O(n^d)$

主定理的推导 Master theorem

猜你喜欢

热点阅读