学习目录
- 1.递归行为时间复杂度
- 2.归并排序
- 1.求小和问题
1.递归行为时间复杂度
需要使用master公式:
T(N) = a * T(N / b) + O(N d)
a:表示在递归函数中递归函数被使用的次数
b:表示每个递归函数计算个数占整体多少份的倒数
O(N d):表示在整个递归函数中除去调用函数的其他代码的时间复杂度
如:
递归函数的代码
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);
}
其master公式为:
T(N) = 2 * T (N / 2) + O(1)
时间的复杂度:
- 当logba < d 时,其时间复杂度为O(Nd)
- logba = d 时,其时间复杂度为O(Nlog(b,a))
- logba > d 时,其时间复杂度为O(Nd * logN)
2.归并排序
原理:
将数组分为左右两部分,分别对左右两部分进行排序;
从左右部分的第一个数进行比较大小,将大(或者小)的数拷贝到一个辅助数组的第一个位置;
取左右部分中已经拷贝的元素的下一位数,与另外部分未拷贝的元素接着比较,并拷贝到辅助数组中,直到左右部分中的其中一部分全部拷贝过一遍;
接着将左右部分中未完全拷贝的部分,按照其当前顺序全部拷贝到辅助数组中;
其代码如下:
//分别将左右部分进行排序
public void 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);
merge(arr,L,mid,R);
}
//将整体进行排序
public void merge(int[] arr,int L,int M,int R){
int[] help = new int[R - L + 1];
int i = 0;
//p1为左边部分的下标,p2为右边部分的下标
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 + 1] = help[i];
}
}
1.求小和问题
在一个数组中,每一个数左边比当前数小的数累加起来,叫做这个数组的小和;
举例:
数组[1,3,4,2,5],其中1左边比1小的数没有,3左边比3小的数为1,以此类推,者可以得到小和为:1+1+3+1+1+3+4+2=16;
解决这个问题可以使用归并排序进行快速的求出小和;
原理:
如上图左边最后一层中,将左右两边进行比较,当右边指针指向的数大于左边指针指向的数时,记录一个左边当前指针的数值,数值即为1,该数值即小和的一部分;
将最后一层的左右数值进行排序,把排好序的数组与上一层进行重复大小比较;
直至将整体数组大小排好序,即可获得小和;
代码:
public void process(int[] arr,int L,int R){
if(L == R)
return arr[L];
int mid = L + ((R - L) >> 1);
//在最开始调用时,第一个函数调用表示整体数组左边产生的小和
//在最开始调用时,第二个函数调用表示整体数组右边产生的小和
//第三个函数调用表示每层左右合并时产生的小和
return process(arr,L,mid) + process(arr,mid + 1,R) + merge(arr,L,mid,R);
}
//将整体进行排序
public 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
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 + 1] = help[i];
}
return res;
}