Master Method Restated-主项定理-递归时间复杂度

对于一个递归实现的分治算法，其时间复杂度表示为：

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

T(N)=aT(n/b)+O(N^d)

b是规模 a是调用次数

其中，a>=1; b>1; h(n)是不参与递归部分的时间复杂度。

比较n^log b (a)与Θ(h(n)) 的大小（Θ的含义和“等于”类似，而大O的含义和“小于等于”类似，感觉好像这里都可以用）：

若n^log b (a)= Θ(h(n)) ：该方法的复杂度为  Θ(h(n)*log(n))

若n^log b (a)< Θ(h(n)) ：该方法的复杂度为  Θ(h(n))

若n^log b (a)> Θ(h(n)) ：该方法的复杂度为  Θ(n^log b (a))

例如：

T(n) = T(n/2)+1：Θ(log(n))（二分查找） T(n) = 2T(n/2)+n ：Θ(n*log(n))（归并排序）

以上都属于“等于”的情况。