01算法笔记
算法第一课
假设寻址操作代价为c；那么便利一个大小为n的数组，代价为nc,称复杂度为o(n);
若代价为（an^2+bn+k）* c，则复杂度为o(n^2)。
二分查找的复杂度o(logn)
复杂度例子
两个有序数组，A中N个元素，B中M个元素，寻找其中相同元素：
- 遍历A中每一个元素，再在B中遍历寻找相同元素，复杂度O(m*n)
- 遍历A中每一个元素，再在B中二分查找相同元素，复杂度O(n*log(m))
- A、B设定两个指针，指向第一个元素，比较二者大小，谁小谁的指针向右移动，若相同同时移动A、B指针，则最差情况下指针移动了M+N的距离，复杂度O(N+M)
这三种情况复杂度分别为O(mn)、O(nlog(m))、O(N+M)，第一个肯定是最糟糕的，后面两种则要分情况讨论，并不能单纯的说第三种好，例如N=4、M=232，第二种为O(4*42）、第三种为O(4+232)
空间复杂度
空间复杂度又称为额外空间复杂度，即为了完成目的所需要的额外的空间。不包括所给的原始空间和输出的空间。
例如一个数组
1 2 3 4 5 | 6 7
需要把“|”左右的交换
一种方法是可以定义一个新的数组，先把6 7放到左边，再放其他的，则需要额外空间7
另外一种方法是：
先对 1 2 3 4 5 在原地进行逆序，为5 4 3 2 1
再对 6 7 逆序，为 7 6
数组变为5 4 3 2 1 | 7 6
再整体逆序，5-6、4-7、3-1
数组变为6 7 | 1 2 3 4 5
则不需要辅助空间（辅助空间只需要交换一个数的，为O(1))。
最优解
在满足时间复杂度最小的情况下，考虑空间复杂度最小的解。
排序
冒泡排序
时间复杂度O(N^2)，额外空间复杂度O(1)，实现可以做到稳定性
6 5 1 2 4 3
开始：
5 6
5 1 6
5 1 2 6
5 1 2 4 6
5 1 2 4 3 6
再将 剩下数 开始进行相同的操作，时间复杂度O(N^2)
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int e = arr.length - 1; e > 0; e--) {
for (int i = 0; i < e; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
}
}
}
}
一个小技巧：对数器
如果想知道一个流程对不对，需要依赖OJ（Online Judge)，还可以依赖对数器。
准备一个容易写不出错的版本，生成随机数据，让两套流程去处理，如果数万次都相同，则可以认为流程正确。
例子：
一个容易写不出错的版本：
public static void comparator(int[] arr) {
Arrays.sort(arr);//调用系统的排序方法
}
生成一个随机数组：
public static int[] generateRandomArray(int maxSize, int maxValue) {
//Math.random()生成double[0,1)
//(int) ((maxSize + 1) * Math.random())->[0,size]整数
//size = 6, size+1 = 7;
//Math.random()*7->double [0,7)
//int 后 [0,6]
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];//生成一个随机长度数组
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}
测试：
//比较两个数组
public static boolean isEqual(int[] arr1, int[] arr2) {
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
return false;
}
if (arr1 == null && arr2 == null) {
return true;
}
if (arr1.length != arr2.length) {
return false;
}
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
public static int[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = arr[i];
}
return res;
}
//打印数组
public static void printArray(int[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 100;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
bubbleSort(arr1);
comparator(arr2);
if (!isEqual(arr1, arr2)) {
succeed = false;
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
int[] arr = generateRandomArray(maxSize, maxValue);
printArray(arr);
bubbleSort(arr);
printArray(arr);
}
对数器的另一个应用：贪心算法
比如在0点到20点有许多课，需要安排课尽量的多。
贪心策略有几种方法，但不知道哪种对
先按哪个课早安排哪个
或
先按哪个课短安排哪个
或
先按哪个更早结束安排哪个（正确的）
如果不知道哪个是对的，自己可以用对数器测试哪种是正确的方法。
选择排序
时间复杂度O(N^2)，额外空间复杂度O(1)，实现可以做到稳定性
就是选最小的放在第一个，第二小的放在第二个...
public static void selectionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
//查找最小的
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}
swap(arr, i, minIndex);
}
}
插入排序
时间复杂度O(N^2)，额外空间复杂度O(1)，实现可以做到稳定性
6 3 2 4
3 6 //插入3，3比6小，交换
3 2 6 //插入2，2比6小，交换
2 3 6 //2比3小，交换
2 3 4 6 //插入4,4比6小，交换
类似于扑克牌整理牌，每次插入到应该的位置。
最好情况完全顺序 O(N)，最坏情况完全逆序 O(N^2)
public static void insertionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
//i从前往后，表示插入的元素；j从后往前，不断比较，找到插入的位置
for (int i = 1; i < arr.length; i++) {
for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
swap(arr, j, j + 1);
}
}
}
三大排序
| 归并排序 | 快速排序 | 堆排序 | |
|---|---|---|---|
| 时间复杂度 | O(N*logN) | O(N*logN) | O(N*logN) |
| 空间复杂度 | O(N) | O(logN) | O(1) |
归并排序
实际是递归，在递归过程中，把父函数压到栈中，再去调用子函数
归并排序就是先把左边部分排好，再把右边部分排好
public static void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
mergeSort(arr, 0, arr.length - 1);
}
public static void mergeSort(int[] arr, int l, int r) {
if (l == r) {
return;
}
int mid = l + ((r - l) >> 1);//>>>高位补0的右移，>>高位补符号位的右移，右移的运算速度比直接除2更快
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l, mid, r);//每个子方法都调用了这个方法，通过它进行了数的交换
}
再进行两个有序数组的排序，
左边右边分别设定两个指针，指向第一个元素，比较二者大小，谁小谁的指针向右移动，把小的放到一个新的数组help去
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];
}
}
过程
5 3 4 6 7 2 9 3
左边：
5 3 4 6
左边 5 3
左边：对5排序，直接RETURN
右边：对3排序，直接RETURN
合并：变成3 5
右边 4 6
左边：对5排序，直接RETURN
右边：对3排序，直接RETURN
合并：变成4 6
合并：变成 3 4 5 6
右边：
略
2 3 7 9
合并：变成 2 3 3 4 5 6 7 9
算法复杂度：
时间复杂度：
T(N) = T(N/2) + T(N/2) + O(N) = 2T(N/2) + O(N)
T为递归过程的复杂度，O(N)为合并的复杂度
使用MASTER公式进行估计。
T(N) = aT(N/b) + O(N^d)
使用Master公式可得，其复杂度为O(Nlogn)
Master公式
关于Master公式的补充可参考：
Master公式的补充
