算法学习3

学习目录

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)

时间的复杂度：

当log_ba < d 时，其时间复杂度为O(N^d)
log_ba = d 时，其时间复杂度为O(N^log(b,a))
log_ba > d 时，其时间复杂度为O(N^d * 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;
}