主方法

遞歸式與分治方法是緊密相關的，因為使用遞歸式可以清晰的刻畫分治算法的運作時間。

主方法如下：

T(n) = aT(n/b) + f(n)

a>=1 b>1 f(n) 是給定的函數。這種形式的遞歸式很常見。刻畫了一個分治算法。生成a個子問題。每個子問題是原來的1/b。分解和合并步驟共消耗f(n)

主方法是計算時間複雜度的時候用的。

利用上面的這個定理就可以計算遞歸式的時間複雜度了，這裡面的1）與3）換句話說就是1)f(n)<nlogb^a 3)意味着f(n)>nlogb^a

T（n） = 9T(n/3) + n 那麼計算其漸進界就是nlog3^9=n^2