剖析递归行为和递归行为时间复杂度的估算
一个递归行为的例子
master公式的使用
2) log(b,a) = d -> 复杂度为O(N^d * logN)
master公式的使用
T(N) = a*T(N/b) + O(N^d)
T(N)是样本量为N时的时间复杂度，N/b是划分成子问题的样本量，子问题发生了a次，后面O(N^d)是除去调用子过程之外的时间复杂度。
比如要求一个数组的最大值：
public static int getMax(int[] arr, int L, int R) {
if (L == R) {
return arr[L];
}
int mid = (L + R) >>> 1;
int maxLeft = getMax(arr, L, mid);
int maxRight = getMax(arr, mid + 1, R);
return Math.max(maxLeft, maxRight);
}
T(N) = 2*T(N/2) + O(1);
这里划分成的递归子过程的样本量是N/2，这个相同的样本量发生了2次，除去调用子过程之外的时间复杂度是O(1),因为求最大值和判断if复杂度是O(1),所以N^d=1，所以d=0.
那么根据如下公式判断
1) log(b,a) > d -> 复杂度为O(N^log(b,a))2) log(b,a) = d -> 复杂度为O(N^d * logN)
3) log(b,a) < d -> 复杂度为O(N^d)
这里log(b, a)(以b为底a的对数) = log(2, 2)=1 > d=0
所以复杂度为O(N^log(2, 2))===>O(N)，因此也就可以解释为什么归并排序的时间复杂度为nlogn了
========================================Talk is cheap, show me the code=======================================
