递归算法复杂性分析-主定理法

主定理

举例：
1）例1：二叉树的遍历。

       T(n)=2T (n/2)+Θ (1) 。

       其中(a=2), (b=2), (f(n)=1), （第一种情况）

       所以 (T(n)=Θ(n)) 。

2）
例1：归并排序。

       T(n)=2T(n/2 )+Θ(n)  。

       其中(a=2), (b=2), (f(n)=n)，此时(k=0)。（第二种情况）

       所以T(n)=Θ(nlogn)

例2：二分搜索（折半搜索）。

       T(n)=T(n/2 )+Θ(1)  。

       其中(a=1), (b=2), (f(n)=1), 此时(k=0),（第二种情况）

       所以T(n)=Θ(log 2 n)。

3）

  设某个算法的复杂性的递推关系式为：T(n)=4T(n/2)+n^3
  很显然，满足主定理第三种情况，只需要取1/2≤c<1即可。T(n)=n^3