Master公式-递归时间复杂度度量

概述

强调一点，所有的递归方法都可以通过循环方法替代，只是递归从逻辑上更容易理解。
Master公式只适用于子问题的规范是一致的，不然无法写成a*T(N/b)。

公式

概念

形如
T(N) = a * T(N/b) + O(N^d) （其中a,b,d都是常数）的递归函数，可以直接通过Master公式来确定时间复杂度。
如果log(b,a) < d，复杂度O(N^d)；
如果log(b,a) > d，复杂度O(N^log(b,a))；
如果log(b,a) == d，复杂度为O(N^d * logN)；
注意：N是处理的总元素数量。
Master公式只关注递归函数整体逻辑，不需要层层的进入递归函数。
N/b表示整体是一次处理的元素个数，a表示元素整体上分成几部分处理，O(N^d)表示合并分支数据的复杂度。

示例

递归版的归并排序。
Master公式说明：
N是arr数组元素的总数。
a = 2，递归方法整体上分成左、右两个分支。
b = 2，每个部分是N/2，所以b为2。
O(N^1)是分支合并的时间复杂度，因此d=1。
所以：log(2,2) == 1，满足log(b,a) = d的公式，
所以归并排序的时间复杂度为O(N * logN)。
我们下面来看归并排序的例子：

package com.study.algorithm.recursion;

public class ArraySort {
    public static void main(String[] args) {
        int[] arr = {1, 3, 9, 18, 5, 6, 7, 13, 22, 19, 38, 39, 61, 89};
        recursionSort(arr, 0, arr.length - 1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + ",");
        }
    }

    public static void recursionSort(int[] arr, int left, int rigth) {
        // base case
        if (left == rigth) {
            return;
        }
        int middle = left + ((rigth - left) >> 2);
        recursionSort(arr, left, middle);
        recursionSort(arr, middle + 1, rigth);
        // 合并分支数据的逻辑
        int[] mergerArr = new int[rigth - left + 1];
        int i = left;
        int j = middle + 1;
        int index = 0;
        while (i <= middle && j <= rigth) {
        	 mergerArr[index++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }
        while (i <= middle) {
            mergerArr[index++] = arr[i++];
        }
        while (j <= rigth) {
            mergerArr[index++] = arr[j++];
        }
        System.arraycopy(mergerArr, 0, arr, left, rigth - left + 1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36