我看網(wǎng)上沒有相關(guān)的推導(dǎo)，于是自己推了一下，算是第一人吧hhhh：

主定理是用來求遞歸式的時間復(fù)雜度常用的方法，然而結(jié)論性語言太多了，不符合我們專業(yè)的特點。所以，我們很有必要從數(shù)學(xué)的角度下解釋遞歸式的時間復(fù)雜度解法。

給出一個遞歸式子：

那么可以將它展開成 a 叉樹，其高度為?logb n?（因為每次遞歸還是分為了 b 份）。

我們可以把這個函數(shù)寫成一般的級數(shù)的形式：

接下來的策略就是，要么將級數(shù)積分近似化，要么就直接展開。

其中，積分近似化為：

例子： 求T(n)=2T(n/2)+nlogn 的時間復(fù)雜度

因此時間復(fù)雜度為O(nlog^2n)