认识时间复杂度为O(NlogN)的排序
剖析递归行为和递归行为时间复杂度的估算
用递归方法找一个数组中的最大值，系统上是怎么做的？
求中点的时候一般不使用(L+R)/2，防止溢出。
public class Code08_GetMax {
public static int getMax(int[] arr){
return process(arr, 0 , arr.length -1);
}
public static 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); //N/2 规模
int rightMax = process(arr, mid + 1, R); //N/2 规模
return Math.max(leftMax,rightMax);
}
}
master公式的使用
T(N) = a*T(N/b) + O(N^d)
- log(b,a) > d —> 复杂度为O(N^log(b,a))
- log(b,a) = d —> 复杂度为O(N^d * logN)
- log(b,a) < d —> 复杂度为O(N^d)
母问题的数据规模为N，子问题的规模每一次都是 N/b， a表示被调用的次数，后面一项是除了子问题之外剩下的过程的时间复杂度。
上面例子的时间复杂度如何计算呢？
T(N) = 2*T(N/2) + O(1) a=2, b=2, d=0; log(2,2)=1 > 0，所以时间复杂度为O(N)
子问题规模一致，就可以使用master公式。
归并排序
public class Code04_MergeSort {
public static void mergeSort(int[] arr){
if (arr == null || arr.length < 2){
return;
}
process(arr, 0, arr.length -1);
}
public static 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);
}
public static 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];
}
}
}
这个也可以是有master公式
T(N) = 2* T(N/2) + O(N)
a= 2, b= 2, d = 1; 复杂度为O(N*logN)
时间复杂度降低了
这个排序方法为什么时间复杂度更低呢？
因为使用了更少的比较行为。比较了N次才进行了一个数
总结
-
整体就是一个简单递归，左边排好序，右边排好序，让整体有序
-
让整体有序的过程里用了排外序方法
-
利用master公式来求解时间复杂度
-
归并排序的实质
例题1
- 小和问题
在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。
【做到不是O(N2)时间复杂度的解法】
例 [1, 3, 4, 2, 5]
相当于计算右边有多少个数比它大，然后加起来就是数组的小和。
可以用归并的方式去计算小和，是不重复不遗漏的。排序的操作不能省略。
相等的时候先拷贝右组
，才能知道有多少个数比它大。
例题2
- 逆序对问题
在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，请打印所有逆序对
荷兰国旗问题
问题1
给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。要求额外空间复杂度O(1),时间复杂度O(N)。
1）设定一个边界标签。当遇到小于num的数时，就跟标签对应的数组数交换，这个标签就加1，遇到大于num的数，就直接无操作，标签不变。
问题2
给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。要求额外空间复杂度O(1),时间复杂度O(N)。[荷兰国旗问题]
设置两个标签，一个是小于的右边界，一个是大于的左边界。
小于num，则进行交换，标签加1，i++
等于num的，不交换。i++
大于num的，和大于区域的前一个交换，标签减1，并且i原地不动，因为后面交换的这个数还没有看过。
当i和大于标签撞到则过程停止。
快排
-
将最后一个数拿出来当做num，然后将左侧的数组分成小于num和大于num的区域。然后交换这个数和大于区域的第一个数，然后这个num的顺序确定了，然后小于和大于的区域进行重复这个过程。
-
快排2.0，利用了荷兰国旗问题的方法，分成了三个区域。
时间复杂度都是O(N2),因为能找到最差的情况。因此还需要改进。因为按照num的值划分，这个结果就可能会导致很坏，比如正好是最大的数。
- 快排3.0
随机产生一个数，跟最后一位交换，然后作为num进行划分。
然后就变成了时间复杂度为 O(N*logN)
public class Code05_QuickSort {
public static void quickSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
quickSort(arr, 0, arr.length - 1);
}
public static 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[l..r]的函数
//默认以arr[r]做划分， arr[r] -> p 分三个区域 <p ==p >p
//返回等于区域的左边界和右边界，res[l,r]
public static int[] partition(int[] arr, int L, int R){
int less = L - 1;
int more = R;
while (L < more){
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};
}
public static void swap(int[] arr, int i, int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
快排的空间复杂度
o(logN) 级别的
最坏的情况是o(N), 最好的情况每次都是中点num。随机情况，趋于o(logN)