master公式 ------ 求递归情况下的时间复杂度

2019-04-29 08:51:42来源：博客园阅读 ()

剖析递归行为和递归行为时间复杂度的估算
一个递归行为的例子
T(N) = a*T(N/b) + O(N^d)
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)

例：

归并排序

 1 public static void mergeSort(int[] arr) {
 2         if (arr == null || arr.length < 2) {
 3             return;
 4         }
 5         mergeSort(arr, 0, arr.length - 1);
 6     }
 7 
 8     public static void mergeSort(int[] arr, int l, int r) {
 9         if (l == r) {
10             return;
11         }
12         int mid = l + ((r - l) >> 1);
13         mergeSort(arr, l, mid);
14         mergeSort(arr, mid + 1, r);
15         merge(arr, l, mid, r);
16     }
17 
18     public static void merge(int[] arr, int l, int m, int r) {
19         int[] help = new int[r - l + 1];
20         int i = 0;
21         int p1 = l;
22         int p2 = m + 1;
23         while (p1 <= m && p2 <= r) {
24             help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
25         }
26         while (p1 <= m) {
27             help[i++] = arr[p1++];
28         }
29         while (p2 <= r) {
30             help[i++] = arr[p2++];
31         }
32         for (i = 0; i < help.length; i++) {
33             arr[l + i] = help[i];
34         }
35     }