Master theorem

$T(n)=aT(\frac{n}{b})+O(n^d)$

上 DSA 用到了就从以前 Blog 上面扒到这里来继续用了（

简要做法

$$Total work = \sum_{0}^{\log_bn}O(n^d)(\frac{a}{b^d})^i$$

这东西是个等比数列,公比为 $(\frac{a}{b^d})$

等比数列的求和公式为

$$S=\frac{a_1(1-q^n)}{1-q}$$

时间复杂度是由最大的那一项决定的对吧，那么分类讨论下公比即可知道哪一项是最大的

公比 < 1

显然等比数列第一项最大，后面逐渐变小

即

$$(\frac{a}{b^d}) < 1 \Rightarrow d > \log_ba$$

$$Total work = O(O(n^d)(\frac{a}{b^d})^0) = O(n^d)$$

公比 > 1

那么是最后一项最大

$$(\frac{a}{b^d}) > 1 \Rightarrow d < \log_ba$$

$$Total work = O(O(n^d)(\frac{a}{b^d})^{\log_bn}) = O(n^d(\frac{a}{b^d})^{\log_bn}) = O(n^d(\frac{a^{\log_bn}}{b^{d\log_bn}}))$$

$$O(n^d(\frac{a^{\log_bn}}{b^{d\log_bn}})) = O(n^d(\frac{a^{\log_bn}}{n^d})) = O(a^{\log_bn})$$

$$a^{\log_bn} = a^{\frac{\log_an}{\log_ab}} = (a^{\log_an})^{\frac{1}{\log_ab}} = n^{\frac{1}{\log_ab}}$$

$$\frac{1}{\log_ab} = \log_ba$$

$$O(a^{\log_bn}) = O(n^{\log_ba})$$

公比 = 1

每一项都一样大，要求和

$$Total work = O(n^d)(1+\log_bn) = O(n^d\log_bn)$$

综上

• 如果 $d > \log_ba$，$T(n) = O(n^d)$
• 如果 $d = \log_ba$，$T(n) = O(n^d\log_bn)$
• 如果 $d < \log_ba$，$T(n) = O(n^{log_ba})$