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

剖析递归行为和递归行为时间复杂度的估算
一个递归行为的例子
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)

例：

归并排序

 public static void mergeSort(int[] arr) {

         if (arr == null || arr.length < 2) {

             return;

         }

         mergeSort(arr, 0, arr.length - 1);

     }

     public static void mergeSort(int[] arr, int l, int r) {

         if (l == r) {

             return;

         }

         int mid = l + ((r - l) >> 1);

         mergeSort(arr, l, mid);

         mergeSort(arr, mid + 1, r);

         merge(arr, l, mid, r);

     }

     public static void merge(int[] arr, int l, int m, int r) {

         int[] help = new int[r - l + 1];

         int i = 0;

         int p1 = l;

         int p2 = m + 1;

         while (p1 <= m && p2 <= r) {

             help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];

         }

         while (p1 <= m) {

             help[i++] = arr[p1++];

         }

         while (p2 <= r) {

             help[i++] = arr[p2++];

         }

         for (i = 0; i < help.length; i++) {

             arr[l + i] = help[i];

         }

     }

T（N） = 2 * T(N/2) + O(N);

log(b,a) = 1==d

所以 T(N) = O(nlogn)

巴特西

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

最新文章

热门文章