递归

wiki-递归

master公式

针对可以将父问题规模``均分成若干子问题的递归，可以用master公式计算时间复杂度
T(N) = a * T(N/b) + O(N^d)

a: 子问题调用次数
b: 父问题均规模是子问题的b倍
O(N^d)：调用外的其他部分的时间复杂度

条件	时间复杂度
log(b,a) < d	O(N^d)
log(b,a) > d	O(N^log(b,a))
log(b,a) = d	O(N^d * logN)

int process(int * a, int l, int r) {
    if (l == r) 
        return a[l];
    int mid = j + (r -l)>>1;
    int left = process(a, l, mid);
    int right = process(a, mid + 1, r);
    return  max(left, right);
}

//上诉递归求最大值里：
//a为2，调用两次递归
//b为2，子问题规模为父问题的一半，
//O(N^d)，就一次比较，时间复杂度为O(1),d为0
//log(2,2) > 0,则O(N^log(b,a)) = O(N^1) = O(N)
//则时间负责都为O(N)