剖析递归行为和递归行为时间复杂度的估算

一个递归行为的例子 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了