摒除一切封建迷信之递归并不难------排序2

阅读量：3936 次

发布时间：2019-05-23

本文共 3889 字，大约阅读时间需要 12 分钟。

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

一个递归行为的例子

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)

补充阅读：www.gocalf.com/blog/algorithm-complexity-and-mastertheorem.html

T(N)表示父问题样本量，T(N/b)表示被拆成子问题的样本量，a表是一共发生多少次，O(n^d)表示除去调用子过程之外，剩下的代价是多少。

什么时候用master公式：划分成子过程的规模是一样的

举例：从一个数组中找最大值

思路：将数组分为左右俩部分，左边（L）最大值和右边（R）最大值比较，最大的数就是最大值。具体代码如下：

public static void main(String[] args) {    int[] arr = {4,3,2,1};    System.out.println(getMax(arr,0,arr.length-1));}private static int getMax(int[] arr, int L, int R) {    if(L == R){        return arr[L];    }    int mid = (L+R)/2;    //maxLeft这个参数指望着   getMax方法返回     保存所有的递归信息，将所有的参数，所有的变量压入栈中    int maxLeft = getMax(arr, L, mid);        int maxRight = getMax(arr, mid + 1, R);    return Math.max(maxLeft,maxRight);}

递归行为时间复杂度

式子一：T(N)= aT（n/b）+O(n^d)

等式左边表示样本大小为n的时间复杂度。

在找出数组最大值的过程中，有等式T(N)= 2*T(n/2)+O(1)，样本量为N/2的过程跑了2次，当跑完这个子过程后，比对较大的数并且返回，是一个常数操作，时间复杂度为O(1)。

所以式子一中 T(n)表示原始大小样本量，n/b 表示子过程的样本量，O(n^d)表示除去调用子过程之外，剩下的代价是多少。

所以，例子中a=2，b=2，d=0

归并排序的细节讲解与复杂度分析

时间复杂度O(N*logN)，额外空间复杂度O(N)

归并排序在上面讲解了递归行为就很简单了。一个数组先左侧部分排好序，再右侧部分排好序。然后整体利用外排的方式排好序。

假设一个数组：5，3，6，）2，0，1，

0）先左侧排好序，再右侧排好序，整体再排好序。左侧部分排好序是3,5,6，而右侧部分排好序是0,1,2，接下来整体排序。

1）准备一个辅助数组，采用外排方式

2）左边部分准备一个下标a指向3，右边准备一个下标b指向0，哪一个小，就向辅助数组插入

则分析公式T(N)= aT（n/b）+O(n^d)，其中a=2，b=2，d=1，所以归并排序时间复杂度为O(N*logN)

具体代码如下：

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;   //准备左侧数组p1指针，指向左侧数组第一个数（即p1是左侧数组最小的值）   int p1 = l;   //准备右侧数组p2指针，指向右侧数组第一个数（即p2是右侧数组最小的值）   int p2 = m + 1;   //这个循环表示谁小，填谁   while (p1 <= m && p2 <= r) {      help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];   }   //当p2已经到达数组末尾，继续填充p1，俩个必有且只有一个越界   while (p1 <= m) {      help[i++] = arr[p1++];   }   while (p2 <= r) {      help[i++] = arr[p2++];   }   //将help数组填回arr   for (i = 0; i < help.length; i++) {      arr[l + i] = help[i];   }}

小和问题和逆序对问题

小和问题

在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。

例子：

[1,3,4,2,5]

1左边比1小的数，没有；

3左边比3小的数，1；

4左边比4小的数，1、3；

2左边比2小的数，1；

5左边比5小的数，1、3、4、2；

所以小和为1+1+3+1+1+3+4+2=16

逆序对问题

在一个数组中，左边的数如果比右边的数大，则折两个数构成一个逆序对，请打印所有逆序对。

这种题可以用归并排序做出解，问题的实质：如果当前数是current，我们找的是，我们查找右边有多少个数比current大，个数*current

举例：

数组1,3,4,2,5

1）先分成左右部分，长度为奇数，左部分可以是3个，也可以是2个，假设分成左边3个。左边1，3，4，右边2，5

2）1,3,4再分治，分为1,3和4；2,5拆成2和5

3）1,3分为1,3

4）merge过程中求所有的小和。

5）准备辅助数组，拷贝1,3，计算小和 1

6）merge1,3和 4，准备一个辅助数组，计算小和 1,3

右侧部分同理，产生小和2

左侧1,3,4，右侧2,5进行最后merge过程产生小和，

1）准备一个辅助数组，左侧a指向1，右侧b指向2

2）a比b小，在右侧有多少个比1 大，包括2在内有2个数，产生 2*1的小和

3）a来到3位置，b是2，a是3，不产生任何小和，然后b来到5位置

4）3比5小，产生一个 1*3 的小和，同时a来到4位置

5）产生一个 1*4 的小和

具体代码如下：

public static int smallSum(int[] arr) {   if (arr == null || arr.length < 2) {      return 0;   }   return mergeSort(arr, 0, arr.length - 1);}public static int mergeSort(int[] arr, int l, int r) {   if (l == r) {      return 0;   }   int mid = l + ((r - l) >> 1);   //左侧部分小和+右侧部分小和+合并过程产生的小和   return mergeSort(arr, l, mid) + mergeSort(arr, mid + 1, r) + merge(arr, l, mid, r);}public static int 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;   int res = 0;   while (p1 <= m && p2 <= r) {//如果p1比p2小，产生的小和      res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;      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];   }   return res;}

除了红色部分，小和问题和归并排序代码一模一样