算法学习3

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)

时间的复杂度：

1. 当log_ba < d 时，其时间复杂度为O(N^d)
2. log_ba = d 时，其时间复杂度为O(N^log(b,a))
3. 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；

解决这个问题可以使用归并排序进行快速的求出小和。