【Master公式】对于这一类符合的递归可以直接确定时间复杂度

Master公式

T(N) = a T(N/b) + O(N^d)
对于这一类符合的递归可以直接确定时间复杂度
a,b,c为常数
1、子问题调用了a次
2、子问题的规模一致，N/b指每个子问题处理总规模/b个规模（只看规模，常数个忽略，如L,mid,mid+1,R）
3、除子问题调用之外的时间复杂度为O(N^d)
结果分为3种情况：
1） log (b) a > d （log以b为底a的对数）
O(N^(log (b) a)
2) log (b) a < d
O(N^d)
3) log (b) a == d
O(N^d * log N)

例1：看process方法是否符合

即快排的递归算法

	 public static void process01(int[] arr, int L, int R){
        if(L >= R){
            return;
        }
        int M = partition(arr, L, R);
        process01(arr, L, M - 1);
        process01(arr, M + 1, R);
    }
1
2
3
4
5
6
7
8

L……R上假设有N个数
子问题1：N/2
子问题2：N/2
b=2:子问题规模一致，数据规模都为N/2，
a=2:子问题调用两次
d=0:其中其他语句时间复杂度O(1)
结果：T(N) = 2T(N/2) + O(N^0) 即2T(N/2) + O(1)
log (2) 2 = 1 > 0
时间复杂度为:O(N) 这里仅仅指递归这个方法的时间复杂度，具体快拍还要乘方法内部复杂度

例2：N个数，max{前2/3N算递归max，后2/3N递归max}

a = 2：调用子问题两次
b = 3/2: 因为N下一个子问题的规模是2/3 * N 相当于N/(3/2)
d = 0: 无其他语句或都为单行规模
结果：T(N) = 2T( N/(3/2) ) + O(d^0)
log(3/2) 2 = 多少？其中

当底数大于1时，真数大的对数大，则 log3 2 当真数相同时，底数大于1时，底数大的对数小，则 log3 12>log4 12
当底数在0到1之间时，真数大的对数小，则 log0.5 2>log0.5 3
当真数相同时，底数在0到1之间时，底数大的对数大，则 log0.5 2

所以 log(3/2) 1 < log(3/2) 2 < log（3/2）3
0 = d < 3/2< log(3/2) 2
时间复杂度为：O( N^(log(3/2) 2) ）

例3：例1 process加一句，打印所有数

即每次进入方法，都要遍历并打印N个数
T= 2T(N/2) + O(N) 除了调用过程之外的复杂度为b个O(N)，因为有一个打印行为
log(b) a = 1 == d -> O(N^d)
时间复杂度为：O(N)