剖析递归行为和递归行为时间复杂度的估算
用递归方法找一个数组中的最大值，系统上到底是怎么做的？
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)
master公式 的理解：
T(N)=a*T(N/b)+O(N^d)
总规模是n的数据量
等量的子规模为N/b
a指调用了a次
O(N^d)指除去子规模之后剩下规模的时间复杂度
求最大值
递归方法求最大值
int getMax(int[] arr) {
return process(arr, 0, arr.length - 1);
}
int process(int[] arr, int L, int R) {
if (L == R) {//整个数组只含有一个数值，直接返回
return arr[L];
}
int mid = L + ((R - L) >> 1);//中点
int leftMax = process(arr, L, mid);
int rightMax = process(arr, mid + 1, R);
return Math.max(leftMax, rightMax);
}
归并排序
工作原理：
整体就是一个简单递归，左边排好序，右边排好序，然后使得整体有序
时间复杂度O(NlogN)
下列代码，利用master公式可得
a=2，b=2，d=1 此时log(2,2) = 1,可得时间复杂度为O(NlogN)
void process(int[] arr, int L, int R) {
if (L == R) {//整个数组只含有一个数值，直接返回
return;
}
int mid = L + ((R - L) >> 1);//中点
process(arr, L, mid);//使得左侧有序
process(arr, mid + 1, R);//使得右侧有序
merge(arr, L, mid, R);
}
/*创建一个辅助空间使得整个数组有序*/
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];
}
}
执行过程：
归并排序的扩展
小和问题：
在一个数组中，每一个数左边比当前数小的数累加起来就，叫做这个数组的小和。求一个数组的小和。
[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
int smallSum(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
return process2(arr, 0, arr.length - 1);
}
int process2(int[] arr, int l, int r) {
if (l == r) {
return 0;
}
int mid = 1 + ((r - 1) >> 1);
return process2(arr, l, mid)
+ process2(arr, mid + 1, r)
+ merge1(arr, l, mid, r);
}
int merge1(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) {
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;
}
如果不理解的话，这里建议自己画一下程序的执行过程（确实难以理解的话，可以私信）
逆序对问题：
在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对。
荷兰国旗问题
问题一
给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)
问题二（荷兰国旗问题）
给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)
思路
1.arr[i]<num,arr[i]和小于区域的下一个数做交换，小于区域右扩，i++
2.arr[i]==num ,i++
3.arr[i]>num,arr[i]和大于区域前一个做交换，大于区域左扩，i不变
理解了问题二的解决方法，问题一就自然而然解决了
快速排序1.0
时间复杂度O(N^2)
给定一个数组arr，将该数组最后一个数据假设为num，将该数组分成左右两部分，左边为小于等于num，右边为大于num，然后将num与右边第一个数做交换，然后重复执行以上步骤
快速排序2.0
时间复杂度O(N^2)
给定一个数组arr，将该数组最后一个数据假设为num，将该数组分成左中右三部分，左边为小于num，中间为等于num，右边为大于num，然后将num与右边第一个数做交换，然后重复执行以上步骤
快速排序3.0
时间复杂度O(NlogN)
给定一个数组arr，随机选取数组一个数据假设为num，，并将num与数组最后一个数据做交换，然后将该数组分成左中右三部分，左边为小于num，中间为等于num，右边为大于num，然后将num与右边第一个数做交换，然后重复执行以上步骤
void quickSort(int[] arr,int L,int R){
if (L < R){
swap(arr,L+(int)(Math.random()*(R - L +1)),R);
int[] p = partition(arr,L,R);
quickSort(arr,L,p[0]-1);//<区
quickSort(arr,p[1]+1,R);//>区
}
}
/**
* 这是一个处理arr[1...r]的函数
* 默认以arr[r]做划分，arr[r] ->p <p ==p >p
* 返回等于区域(左边界，右边界)，所以返回一个长度为2的数组res，res[0]res[1]
* */
int[] partition(int[] arr,int L,int R){
int less = L-1;//<区右边界
int more = R;//>区左边界
while (L < more){//L表示当前数的位置 arr[R] -> 划分值
if (arr[L] < arr[R]){//当前数 < 划分值
swap(arr,++less,L++);
} else if (arr[L] > arr[R]) {//当前数 > 划分值
swap(arr,--more,L);
}else {//当前数 == 划分值
L++;
}
}
swap(arr,more,R);
return new int[] {less + 1,more};
}
void swap(int[] arr,int i,int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}