关于递推问题算法复杂度的的推导。
递推公式：\[ \label{eq1} T(n) = aT(\frac{n}{b})+O(n^{d}), a>0,b>1,d\geq 0\]
分三种情况: \[ \label{eq2} 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) \]