算法之使用Master Theorem估算时间复杂度算法时间复杂度归并排序

遇到递归算法，通常有两个问题：

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

【算法之使用Master Theorem估算时间复杂度】使用树状分析图可以帮助我们剖析递归行为。
使用Master Theorem及其推论（也称主定理）可以方便的估算某些递归的时间复杂度。
这里主要针对第二个问题，如何针对某类递归，使用master公式估算时间复杂度。
主定理先来看下公式以及结论：

文章图片

先理解公式里面每一项代表的意义：
等号左边T(N)是母问题的数据量，规模为N。
等号右边的T(N/b)是子问题的规模，子问题的规模是等量的，规模为N/b；系数a是子问题被调用的次数；O(N^d)是指除了子问题的递归调用之外，剩下的运算的时间复杂度。
满足以上描述的递归，可以使用主定理来估算时间复杂度。
下面使用两个例子来训练一下。
例1

写一个递归方法，来找到数组中的最大值。

static int findMax(int[] arr) throws IllegalArgumentException{ if (arr == null || arr.length == 0) throw new IllegalArgumentException("invalid."); if (arr.length == 1) return arr[0]; return recursion(arr, 0, arr.length - 1); }private static int recursion(int[] arr, int from, int to) { if (from == to) return arr[from]; int mid = from + (to - from) / 2; int left = recursion(arr, from, mid); int right = recursion(arr, mid + 1, to); return Math.max(left, right); }

在上面的问题中，母问题总量是N，也就是数组的长度；递归函数中，子问题被调用了两次，也就是系数a=2，分别用来计算左半子数组和右半子数组的最大值，规模是等量的，都是是N/2；剩下的操作就是if判断，计算mid值，返回left和right较大值，这些操作的时间复杂度是常数O(1)。完全满足主定理的场景。T(N) = 2 * T(N/2) + O(N^0): a=2, b=2, d=0.
log(b,a) = log(2,2) = 1 > d = 0, 所以用推论直接得出复杂度是T(N)=O(N).
例2 用主定理来估算归并排序算法的复杂度。
归并排序先递归地将数组分成两半，分别排序，然后将结果归并起来。算法如下：

public class MergeSort { static void mergeSort(int[] arr) { if (arr == null || arr.length < 2) return; sort(arr, 0, arr.length - 1); }static void sort(int[] arr, int left, int right) { if (left >= right) return; int mid = left + (right - left) / 2; sort(arr, left, mid); sort(arr, mid + 1, right); merge(arr, left, mid, right); }private static void merge(int[] arr, int left, int mid, int right) { int[] help = new int[right - left + 1]; // 1. 把arr[left, mid]和arr[mid+1, right]两个子数组归并到辅助数组// a指向第一个子数组的起始位置，b指向第二个子数组的起始位置，指向辅助数组的起始位置 int i = 0, a = left, b = mid + 1; // 在a和b不越界的情况下，比较所指的元素，把较小的那个放到辅助数组中 while (a <= mid && b <= right) { help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++]; } // 若a不越界，说明b已经越界，把左边的子数组剩下的元素依次放入辅助数组 while (a <= mid) { help[i++] = arr[a++]; } // 若b不越界，说明a已经越界，把右边的子数组剩下的元素依次放入辅助数组 while (b <= right) { help[i++] = arr[b++]; } // 2. 把辅助数组中的元素拷贝回arr数组 for (i = 0; i < help.length; i++) { arr[left + i] = help[i]; } }static boolean checkSorted(int[] arr) { if (arr.length < 2) return true; for (int i = 1; i < arr.length; i++) { if (arr[i] < arr[i - 1]) return false; } return true; }public static void main(String[] args) { int n = 1000000; int[] arr = new int[n]; for (int i = 0; i < n; i++) arr[i] = (int) (Math.random() * n); mergeSort(arr); System.out.println(checkSorted(arr)); } }

母问题总量是数组长度N，在递归体中子问题规模相等，都是N/2，调用了两次；判断语句和计算mid语句是常数级运算O(1)，merge方法的复杂度是O(N),因为在merge中，最坏的情况是把数组所有元素往辅助数组中放一遍，又从辅助数组往原数组中放一遍，所以复杂度是O(N)。
这种情况满足主定理条件，T(N)=2T(N/2)+O(N), a = 2, b = 2, d = 1.
利用推论log(b,a)=1 和 d 相等，所以直接计算复杂度T(N)=O(N*logN).
注意：若子问题规模不相等，则不符合使用主定理的条件。