递归
剖析递归行为和递归行为时间复杂度的估算
用递归方法找一个数组中的最大值，系统上到底是怎么做的?
import java.util.Arrays;public class GetMax {public static int getMax(int[] arr) {return getLocalMax(arr, 0, arr.length - 1);}public static int getLocalMax(int[] arr, int L, int R) {System.out.println("R为 " + R + " L为 " + L);if (L == R) return arr[L];// 中点int mid = L + ((R - L) >> 1);int lMax = getLocalMax(arr, L, mid);int rMax = getLocalMax(arr, mid + 1, R);return Math.max(lMax, rMax);}public static void main(String[] args) {// 生成一个随机数组int[] arr = ArrayGenerator.getArr(11, 30);System.out.println(Arrays.toString(arr));System.out.println("最大值为：" + GetMax.getMax(arr));}}
master 公式的使用
T(N)=a*T(N/b)+O(N^d)
：母问题一共有 N 个数据，即规模是 
：是子问题的规模，即每个子问题有 
，
就是子问题被调用了 a 次，这里就要求必须是等规模的才能用 master 公式来求解
：除去子问题之外的其他过程的时间复杂度
上面的例子 用递归方法找一个数组中的最大值：在 getLocalMax 中，每个子问题是解决母问题一般的数据，规模为 
，一共调用了 2 次，额外的时间复杂度是计算中点 int mid = L + ((R - L) >> 1); 也就是 
，a = 2，b = 2，d = 0，最后的结果为 
规律：
复杂度为 
复杂度为 
复杂度为
补充阅读： www.gocalf.com/blog/algorithm-complexity-and-master-theorem.html
归并排序
- 整体就是一个简单递归，左边排好序、右边排好序、让其整体有序
- 让其整体有序的过程里用了外排序方法
- 利用 master 公式来求解时间复杂度
- 归并排序的实质
import java.util.Arrays;public class MergeSort {private static void sort(int[] arr) {process(arr, 0, arr.length - 1);}private 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);}// 合并private static void merge(int[] arr, int L, int M, int R) {int[] temp = new int[R - L + 1];int i = 0;int lP = L;int rP = M + 1;// 哪个小就先保存哪个，直到一个数组越界while (lP <= M && rP <= R) {temp[i++] = arr[lP] < arr[rP] ? arr[lP++] : arr[rP++];}// 将其他的数保存到数组中while (lP <= M) {temp[i++] = arr[lP++];}while (rP <= R) {temp[i++] = arr[rP++];}// 将排好序的数组保存到 arr 中for (int j = 0; j < temp.length; j++) {arr[L + j] = temp[j];}}public static void main(String[] args) {int[] arr = ArrayGenerator.getArr(5, 30);System.out.println(Arrays.toString(arr));MergeSort.sort(arr);System.out.println(Arrays.toString(arr));}}
额外的复杂度是merge操作，merge是数组数据拷贝，复杂度为
，即归并排序整体规模为 
，a=2,b=2,d=1，
即时间复杂度 
，额外空间复杂度
归并排序的扩展
- 小和问题
在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。
例子：[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
思路：这里的左侧的最小和可看做是：右侧有 n 个数比当前数大：
1 右边比 1 大的数，3、4、2、5 共 4 个
3 右边比 3 大的数，4、5 共 2 个
4 右边比 4 大的数，5 一个
2 右边比 2 大的数，5 一个
5 右边比 5 大的数，没有
所以小和为 14 + 32 + 41 + 21 =16，可以使用归并排序来判断右侧有多少个数比当前数大
import java.util.Arrays;public class SmallSum {static int sum = 0;public static int smallSum(int[] arr) {sum = 0;process(arr, 0, arr.length - 1);return sum;}private 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);}// 合并private static void merge(int[] arr, int L, int M, int R) {int[] temp = new int[R - L + 1];int i = 0;int lP = L;int rP = M + 1;while (lP <= M && rP <= R) {if (arr[lP] < arr[rP]) {// 说明右侧有 R - rP + 1 个数比 temp[i] 大temp[i] = arr[lP];System.out.println(temp[i] + "*" + (R - rP + 1));sum += temp[i] * (R - rP + 1);lP++;} else {temp[i] = arr[rP];rP++;}i++;}// 将其他的数保存到数组中while (lP <= M) {temp[i++] = arr[lP++];}while (rP <= R) {temp[i++] = arr[rP++];}// 将排好序的数组保存到 arr 中for (int j = 0; j < temp.length; j++) {arr[L + j] = temp[j];}}public static void main(String[] args) {int[] arr = new int[]{1, 3, 4, 2, 5};System.out.println(Arrays.toString(arr));System.out.println(smallSum(arr));int[] arr1 = ArrayGenerator.getArr(5, 20);System.out.println(Arrays.toString(arr1));System.out.println(smallSum(arr1));}}
另一种写法：思路是一致的
import java.util.Arrays;public class SmallSum1 {public static int smallSum(int[] arr) {return process(arr, 0, arr.length - 1);}private static int process(int[] arr, int L, int R) {if (L == R) return 0;int mid = L + ((R - L) >> 1);return process(arr, L, mid) + process(arr, mid + 1, R) + merge(arr, L, mid, R);}// 合并private static int merge(int[] arr, int L, int M, int R) {int sum = 0;int[] temp = new int[R - L + 1];int i = 0;int lP = L;int rP = M + 1;while (lP <= M && rP <= R) {if (arr[lP] < arr[rP]) {// 说明右侧有 R - rP + 1 个数比 temp[i] 大temp[i] = arr[lP];System.out.println(temp[i] + "*" + (R - rP + 1));sum += temp[i] * (R - rP + 1);lP++;} else {temp[i] = arr[rP];rP++;}i++;}// 将其他的数保存到数组中while (lP <= M) {temp[i++] = arr[lP++];}while (rP <= R) {temp[i++] = arr[rP++];}// 将排好序的数组保存到 arr 中for (int j = 0; j < temp.length; j++) {arr[L + j] = temp[j];}return sum;}public static void main(String[] args) {int[] arr = new int[]{1, 3, 4, 2, 5};System.out.println(Arrays.toString(arr));System.out.println(smallSum(arr));int[] arr1 = ArrayGenerator.getArr(5, 20);System.out.println(Arrays.toString(arr1));System.out.println(smallSum(arr1));}}
- 逆序对问题
在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，请打印所有逆序对。
例如：[3,2,4,5,0]，就存在逆序对 [3,2] [3,0], [2,0] [4,0], [5,0]
思路：和上面的求小和思路一致
import java.util.Arrays;
public class ReverseOrderArr {
public static void reverseOrder(int[] arr) {
process(arr, 0, arr.length - 1);
}
private 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);
}
private static void merge(int[] arr, int L, int M, int R) {
int lP = L;
int rP = M + 1;
while (lP <= M && rP <= R) {
if (arr[lP] > arr[rP]) {
System.out.println("[" + arr[lP] + "," + arr[rP] + "]");
lP++;
} else {
rP++;
}
}
}
public static void main(String[] args) {
int[] arr = new int[]{3, 2, 4, 5, 0};
System.out.println(Arrays.toString(arr));
ReverseOrderArr.reverseOrder(arr);
int[] arr1 = ArrayGenerator.getArr(5, 20);
System.out.println(Arrays.toString(arr1));
ReverseOrderArr.reverseOrder(arr1);
}
}
荷兰国旗问题
- 问题一
给定一个数组 arr，和一个数 num，请把小于等于 num 的数放在数组的左边，大于 num 的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)
import java.util.Arrays;
public class SplitArr {
private static void splitArr(int[] arr, int num) {
// >= num 的第一个数的下标
int index = -1;
for (int i = 0; i < arr.length; i++) {
int cur = arr[i];
if (cur > num) {
if (index == -1) index = i;
} else if (cur == num) {
if (index == -1) {
index = i;
} else {
arr[index] = arr[index] ^ arr[i];
arr[i] = arr[index] ^ arr[i];
arr[index] = arr[index] ^ arr[i];
}
} else {
if (index != -1 && i > index) {
System.arraycopy(arr, index, arr, index + 1, i - index);
arr[index++] = cur;
}
}
}
}
public static void main(String[] args) {
int[] arr = new int[]{1, 3, 5, 7, 4, 2, 6};
System.out.println(Arrays.toString(arr));
splitArr(arr, 4);
System.out.println(Arrays.toString(arr));
}
}
- 问题二（荷兰国旗问题）
给定一个数组 arr，和一个数 num，请把小于 num 的数放在数组的左边，等于 num 的数放在数组的中间，大于num的数放在数组的右边。要求额外空间复杂度 O(1)，时间复杂度 O(N)
思路：
确认数组的大于或者小于的边界。遍历数组
- 当前数小于 num，和小于的边界 + 1 交换，小于区右扩，i++
- 相等，直接跳过，i++
- 当前数大于 num，和大于的边界 - 1 交换，大于区左扩，i 不变
这个思路也可以解决问题一
import java.util.Arrays;
public class DutchFlag {
private static void splitArr(int[] arr, int num) {
// 小于的边界
int lIndex = -1;
// 大于的边界
int rIndex = arr.length;
int i = 0;
while (i < rIndex) {
int cur = arr[i];
if (cur < num) {
// 小于，和小于的边界+1交换，小于区右扩
lIndex++;
if (i != lIndex) {
arr[i] = arr[i] ^ arr[lIndex];
arr[lIndex] = arr[i] ^ arr[lIndex];
arr[i] = arr[i] ^ arr[lIndex];
}
i++;
} else if (cur == num) {
// 相等，直接跳过
i++;
} else {
// 大于，和大于的边界交换-1，大于区左扩，i不变
rIndex--;
if (i != rIndex) {
arr[i] = arr[i] ^ arr[rIndex];
arr[rIndex] = arr[i] ^ arr[rIndex];
arr[i] = arr[i] ^ arr[rIndex];
}
}
}
}
public static void main(String[] args) {
int[] arr = new int[]{1, 3, 5, 7, 4, 2, 6, 4};
System.out.println(Arrays.toString(arr));
splitArr(arr, 4);
System.out.println(Arrays.toString(arr));
}
}
快速排序
基本思路是：
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。
1.0 版本
在整个数组中，拿最后一个数来划分 2 部分，即就将最后一个数来作为 num ，比 num 小的放到 num 前，比 num 小的放到后面
2.0 版本
在 1.0 的基础上，将数组划分为 3 部分，分别为大于 num，等于 num，小于 num。这样后续的划分中就可以不用处理等于 num 的部分
3.0 版本
不论是 1.0 还是 2.0 版本，时间复杂度都是 
，都有最差的情况：每次划分取的最后一个数都是最大值，如：[1,2,3,4,5,6]，每次划分都只是能确定一个数的位置
最差的情况原因：划分数组的值很“偏”，不能很好的划分数组。相反，如果每次划分值都能在中间位置把数组划分成数据量基本相等几个部分，算法的效率就会提高很多
在 2.0 的基础上，每次做数组划分时，在区间范围内随机取一个数和区间最后一个数交换，然后保持原来的逻辑使用最后一个数作为 num 来划分数组。这里使用随机选数来，也就是说所有的情况都会等概率出现，复杂度就会优化为
import java.util.Arrays;
import java.util.Random;
public class QuickSort {
public static void sort(int[] arr) {
partition(arr, 0, arr.length);
}
public static void partition(int[] arr, int L, int R) {
if (L >= R) return;
// System.out.println(arr[L] + " " + arr[R-1]);
// 小于的边界
int lIndex = L - 1;
// 大于的边界
int rIndex = R;
// 分区参照下标
int num = arr[L + new Random().nextInt(R - L)];
int i = L;
while (i < rIndex) {
int cur = arr[i];
if (cur < num) {
// 小于，和小于的边界+1交换，小于区右扩
lIndex++;
if (i != lIndex) {
arr[i] = arr[i] ^ arr[lIndex];
arr[lIndex] = arr[i] ^ arr[lIndex];
arr[i] = arr[i] ^ arr[lIndex];
}
i++;
} else if (cur == num) {
// 相等，直接跳过
i++;
} else {
// 大于，和大于的边界交换-1，大于区左扩，i不变
rIndex--;
if (i != rIndex) {
arr[i] = arr[i] ^ arr[rIndex];
arr[rIndex] = arr[i] ^ arr[rIndex];
arr[i] = arr[i] ^ arr[rIndex];
}
}
}
// System.out.println(num);
// System.out.println(Arrays.toString(arr));
// 这里要注意修改边界
partition(arr, L, lIndex + 1);
partition(arr, rIndex, R);
}
public static void main(String[] args) {
int[] arr = ArrayGenerator.getArr(15, 100);
System.out.println(Arrays.toString(arr));
sort(arr);
System.out.println(Arrays.toString(arr));
// 对数，确保正确
for (int i = 0; i < 100; i++) {
arr = ArrayGenerator.getArr(15, 100);
int[] arr1 = ArrayGenerator.getSortArr(arr);
sort(arr);
if (!ArrayGenerator.isSame(arr, arr1)) {
System.out.println("出错了：" + Arrays.toString(arr));
}
}
}
}
快速排序的空间复杂度的在 3.0 版本情况为
若有收获，就点个赞吧
0 人点赞
