前提：如果一个问题可以拆分为多个等规模的子问题进行递归求解

则其时间复杂度满足master公式：

T(n) = a * T(n/b) + O(n^d);

其中T(n)表示问题规模为n的母问题的时间复杂度     

　　T(n/b)表示问题规模拆分为n/b的子问题的时间复杂度

　　a表示子问题在每次递归时的执行的次数(不是总的执行次数)

　　O(n^d)表示除了拆分子问题外，每次递归时还要进行的其他操作的时间复杂度。

master公式的求解(记住结论)：

1.如果log b (a) < d  则：O(n^d)  即此时由额外操作做为主要的时间复杂度

2.如果log b (a) > d  则：O(n^log b (a)) 即此时递归为主要的时间复杂度

3.如果log b (a) == d 则：O(n^d * log (n)) 即此时两者都要考虑,因为每一层额外操作要做n^d次，且有log(n)层

用以上公式分析以下代码的时间复杂度：

1 //用递归求数组的最大值
2     public static int process(int[] arr,int l,int r)
3     {
4         if (l == r) return arr[l];
5         int mid = l + ((r - l) >> 1);//此处(r-l)>>1一定要加括号,因为>>的运算级比+低
6         int leftMax = process(arr,l,mid);
7         int rightMax = process(arr,mid + 1,r);
8         return Math.max(leftMax, rightMax);
9     }

从代码中得，每次都将规模为n的子问题拆成了规模为n/2的子问题，且每次递归中，子问题都执行了2次(leftMax一次，rightMax一次)

且额外的操作就是Math.max(leftMax,rightMax),所以时间复杂度为O(1)

所以得到式子：T(n) = 2 * T(n / 2) + O(1)

即：a = b = 2 , d= 0

所以解得时间复杂度为 O(n)

用以上公式分析归并排序的算法时间复杂度：

 1 public static void MergeSort(int[] arr)
 2     {
 3         if (arr.length == 1 || arr == null) {
 4             return;
 5         }
 6         process(arr,0,arr.length - 1);
 7     }
 8     
 9     //递归进行划分子问题的排序
10     public static void process(int[] arr,int l,int r)
11     {
12         if (l == r) {
13             return;
14         }
15         int mid = l + ((r - l) >> 1);
16         process(arr,l,mid);
17         process(arr,mid + 1,r);
18         Merge(arr,l,mid,r);
19     }
20     
21     //对两个有序的数组分布进行排序
22     public static void Merge(int[] arr,int l,int mid,int r)
23     {
24         int i = l , j = mid + 1;
25         int[] help = new int[r - l + 1];
26         int cnt = 0;
27         while (i <= mid && j <= r) {
28             help[cnt++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
29         }
30         while (i <= mid) {
31             help[cnt++] = arr[i++];
32         }
33         while (j <= r) {
34             help[cnt++] = arr[j++];
35         }
36         for (int k = 0; k < r - l + 1 ; k++)
37         {
38             arr[k + l] = help[k];
39         }
40 　　　}

所以T(n) = 2 * T(n / 2) + O(n)

所以 a = b = 2, d = 1;

所以时间复杂度为O(n * log n)