年輕即出發(fā)...
簡書：http://www.itdecent.cn/u/7110a2ba6f9e
知乎：https://www.zhihu.com/people/zqtao23/posts
GitHub源碼：https://github.com/zqtao2332
個(gè)人網(wǎng)站：http://www.zqtaotao.cn/ （停止維護(hù)更新內(nèi)容，轉(zhuǎn)移簡書）
? 咆哮怪獸一枚...嗷嗷嗷...趁你現(xiàn)在還有時(shí)間，盡你自己最大的努力。努力做成你最想做的那件事，成為你最想成為的那種人，過著你最想過的那種生活。也許我們始終都只是一個(gè)小人物，但這并不妨礙我們選擇用什么樣的方式活下去，這個(gè)世界永遠(yuǎn)比你想的要更精彩。
最后：喜歡編程，對(duì)生活充滿激情
本節(jié)內(nèi)容預(yù)告
算法時(shí)間復(fù)雜度評(píng)定標(biāo)準(zhǔn)
實(shí)例1：一個(gè)簡單的理解時(shí)間復(fù)雜度的例子
實(shí)例2：冒泡排序
實(shí)例3：選擇排序
實(shí)例4：插入排序
實(shí)例5：對(duì)數(shù)器
實(shí)例6：理解遞歸行為，以及遞歸行為事件復(fù)雜度的估算
實(shí)例7：歸并排序
實(shí)例8：小和問題和逆序?qū)栴}
算法的評(píng)定標(biāo)準(zhǔn)有兩個(gè)-時(shí)間復(fù)雜度，空間復(fù)雜度
1、常數(shù)時(shí)間的操作：一個(gè)操作如果和數(shù)據(jù)量沒有關(guān)系，每次都是固定時(shí)間內(nèi)完成的操作，叫做常數(shù)操作。+
例如：
- 加減乘除
- 位運(yùn)算
- 數(shù)組尋址
這些操作的時(shí)間和樣本是數(shù)據(jù)量是沒有關(guān)系的
時(shí)間復(fù)雜度是一個(gè)算法流程中，評(píng)價(jià)常數(shù)操作數(shù)量的指標(biāo)。
常用O（讀作big O）來表示，具體，在常數(shù)操作數(shù)量的表達(dá)式中，只要高階項(xiàng)，不要低階項(xiàng)，也不要高階項(xiàng)的系數(shù)，剩下的部分如果記為f(N), 那么時(shí)間復(fù)雜度為O(f(N))。
評(píng)價(jià)算法流程好壞
評(píng)價(jià)一個(gè)算法流程的好壞，先看時(shí)間復(fù)雜度的指標(biāo)，然后在分析不同數(shù)據(jù)樣本下的實(shí)際運(yùn)行時(shí)間，也就是常數(shù)項(xiàng)時(shí)間。
如：第一種算法流程的時(shí)間復(fù)雜度指標(biāo)為N，所以他的算法好一些。（當(dāng)然數(shù)據(jù)樣本非常小，第二種好一些）
實(shí)例·1
一個(gè)簡單的理解時(shí)間復(fù)雜度的例子
一個(gè)有序數(shù)組A，另一個(gè)無序數(shù)組B，請(qǐng)打印B中的所有不在A中的數(shù)，A數(shù) 組長度為N，B數(shù)組長度為M。
可以使用三種常用的算法流程來解決這個(gè)問題：
算法流程1：對(duì)于數(shù)組B中的每一個(gè)數(shù)，都在A中通過遍歷的方式找一下；
算法流程2：對(duì)于數(shù)組B中的每一個(gè)數(shù)，都在A中通過二分的方式找一下；
算法流程3：先把數(shù)組B排序，然后用類似外排的方式打印所有不在A中出現(xiàn) 的數(shù)；
三個(gè)流程，三種時(shí)間復(fù)雜度的表達(dá)...
如何分析好壞？
流程1
時(shí)間復(fù)雜度：O(N*M)
流程2
二分法：每次排除一半的樣本數(shù)據(jù)
時(shí)間復(fù)雜度：O(M*logN)
ps : logN是以2為底
流程3
先排序 O(M*logM)
外排比較時(shí)間復(fù)雜度：O(N + M)
總結(jié)，流程1性能最差；如果A長，B短，流程2好；如果A短，B長，流程3好；
實(shí)例2
冒泡排序
每次相鄰的兩個(gè)數(shù)進(jìn)行比較，然后交換（需要時(shí)交換），每一趟都找到了當(dāng)前樣本中的最大數(shù)
// 排序
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length < 2)
return;
// 每一趟少一個(gè)最大元素，固定范圍
for (int end = arr.length - 1; end > 0; end--) {
for (int i = 0; i < end; i++) { // i 不能= end ，不然 i + 1 數(shù)組越界
if (arr[i] > arr[i + 1])
swap(arr, i, i + 1);
}
}
// 打印結(jié)果
System.out.println(Arrays.toString(arr));
}
// 交換
public static void swap(int[] arr, int i, int j) {
// 交換時(shí)間復(fù)雜度：常數(shù)時(shí)間復(fù)雜度
// 交換只涉及到了數(shù)組元素的尋址操作，這是常數(shù)時(shí)間操作
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
時(shí)間復(fù)雜度O(N^2)，額外空間復(fù)雜度O(1)
實(shí)例3
選擇排序
每次選擇一個(gè)最小的放在該放的位置上
public static void selectionSort(int[] arr) {
if (arr == null || arr.length < 2)
return;
/*
5 9 4 1 2
第一次 i = 0, 循環(huán)完畢找到 數(shù)1 的下標(biāo)，交換數(shù)，將1 放到 第0 個(gè)位置上
交換后結(jié)果：1 9 4 5 2
第二次 i = 1, 循環(huán)完畢找到 數(shù)2 的下標(biāo)，交換數(shù)，將2 放到 第1 個(gè)位置上
交換后結(jié)果：1 2 4 5 9
依次類推 ...5 個(gè)數(shù)，需要循環(huán)4次
*/
// 外層規(guī)定循環(huán)范圍, 每次找到最小的數(shù)，放在第 i 個(gè)位置上
// N個(gè)元素，當(dāng)前N-1 個(gè)位置上的數(shù)已經(jīng)確定，則最后一個(gè)也是確定的，所以 i < arr.length - 1
for (int i = 0; i < arr.length - 1; i++) {
// 假設(shè)當(dāng)前 i 位置上的數(shù)就是最小數(shù)
int minIndex = i;
// 內(nèi)層尋找最小數(shù)下標(biāo)
for (int j = i + 1; j < arr.length; j++) {
minIndex = arr[minIndex] < arr[j] ? minIndex : j;
}
swap(arr, i, minIndex);
}
System.out.println(Arrays.toString(arr));
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
時(shí)間復(fù)雜度O(N^2)，額外空間復(fù)雜度O(1)
實(shí)例4
插入排序
算法時(shí)間復(fù)雜度
插入排序和選擇排序，冒泡排序不同，它跟數(shù)據(jù)的狀態(tài)有關(guān)。
最好情況：數(shù)據(jù)是有序的如：1 2 3 4 5，O(N)
最壞情況：數(shù)據(jù)是反序的如：5 4 3 2 1, 求小到大序，則O(N^2)
時(shí)間復(fù)雜度O(N^2)，額外空間復(fù)雜度O(1)
將數(shù)據(jù)組劃分為兩塊，一塊是已經(jīng)排序好的，一塊是待排序的
每一次從待排序數(shù)組中取出一個(gè)元素，進(jìn)行插入
插入選擇：從排序好的數(shù)組的最后一個(gè)元素開始進(jìn)行倒序遍歷，尋找它應(yīng)該存放的位置，進(jìn)行交換插入
實(shí)例5
對(duì)數(shù)器
采用對(duì)數(shù)器來進(jìn)行驗(yàn)證
1、一個(gè)你想要測(cè)試的方法 a
2、一個(gè)絕對(duì)正確但是復(fù)雜度不好是方法 b
3、實(shí)現(xiàn)一個(gè)隨機(jī)樣本產(chǎn)生器
4、實(shí)現(xiàn)對(duì)比的方法
5、把方法a和方法b比對(duì)很多次來驗(yàn)證方法a 是否正確
6、如果有一個(gè)樣本使得對(duì)比出錯(cuò)，打印出樣本，分析到底是哪個(gè)方法出錯(cuò)
7、當(dāng)樣本數(shù)量很多時(shí)比對(duì)測(cè)試依然正確，可以確定方法a 正確
測(cè)試一下插入排序
模型
import java.util.Arrays;
/**
* @description: 排序隨機(jī)樣本產(chǎn)生器模型
* @version: 1.0
*/
public class SortModel {
// for test : 一個(gè)絕對(duì)正確的排序方法 --> 這里使用Java自帶方法
public static void comparator(int[] arr) {
Arrays.sort(arr);
}
// for test : 隨機(jī)樣本產(chǎn)生器
public static int[] generateRandomArray(int maxSize, int maxValue) {
// 隨機(jī)數(shù)組長度，隨機(jī)長度
int[] arr = new int[(int) (Math.random() * (maxSize + 1))];
// 隨機(jī)數(shù)據(jù)
for (int i = 0; i < arr.length; i++) {
// 兩個(gè)隨機(jī)數(shù)相減，可以隨機(jī)出負(fù)數(shù)
arr[i] = (int) (Math.random() * (maxValue + 1)) - (int) (Math.random() * (maxValue + 1));
}
return arr;
}
// for test : 復(fù)制數(shù)組
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;
}
// for test : 實(shí)現(xiàn)一個(gè)對(duì)比方法
public static boolean isEqual(int[] arr1, int[] arr2) {
// 有一個(gè)數(shù)組為null
if (arr1 == null && arr2 != null
|| arr1 != null && arr2 == null)
return false;
// 兩個(gè)數(shù)組都為null
if (arr1 == null && arr2 == null) return true;
// 兩個(gè)數(shù)組的長度不一致
if (arr1.length != arr2.length) return false;
// 對(duì)比兩個(gè)數(shù)組中的每一個(gè)元素
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i])
return false;
}
return true;
}
/*
采用對(duì)數(shù)器來進(jìn)行驗(yàn)證
1、一個(gè)你想要測(cè)試的方法 a
2、一個(gè)絕對(duì)正確但是復(fù)雜度不好是方法 b
3、實(shí)現(xiàn)一個(gè)隨機(jī)樣本產(chǎn)生器
4、實(shí)現(xiàn)對(duì)比的方法
5、把方法a和方法b比對(duì)很多次來驗(yàn)證方法a 是否正確
6、如果有一個(gè)樣本使得對(duì)比出錯(cuò)，打印出樣本，分析到底是哪個(gè)方法出錯(cuò)
7、當(dāng)樣本數(shù)量很多時(shí)比對(duì)測(cè)試依然正確，可以確定方法a 正確
*/
}
測(cè)試
import cn.zqtao.learn.model.SortModel;
import java.util.Arrays;
/**
* @description: 插入排序（相對(duì)工程中使用挺多）
* <p>
* 類似插牌
* <p>
* 將數(shù)據(jù)組劃分為兩塊，一塊是已經(jīng)排序好的，一塊是待排序的
* <p>
* 每一次從待排序數(shù)組中取出一個(gè)元素，進(jìn)行插入
* 插入選擇：從排序好的數(shù)組的最后一個(gè)元素開始進(jìn)行倒序遍歷，尋找它應(yīng)該存放的位置，進(jìn)行交換插入
* @version: 1.0
*/
public class Code_02_InsertionSort {
public static void insertionSort(int[] arr) {
if (arr == null || arr.length < 2)
return;
// 外層循環(huán)控制循環(huán)次數(shù), 默認(rèn)認(rèn)為第一個(gè)元素是已經(jīng)排序好的
for (int i = 1; i < arr.length; i++) {
// 對(duì)已經(jīng)排序好的數(shù)組進(jìn)行倒敘遍歷，查詢新元素的插入下標(biāo)
for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
swap(arr, j, j + 1);
}
}
}
// 不需要使用臨時(shí)變量，進(jìn)行交換
public static void swap(int[] arr, int i, int j) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
public static void main(String[] args) {
int testTime = 5000;
int maxSize = 10;
int maxValue = 100;
for (int i = 0; i < testTime; i++) {
int[] randomArr = SortModel.generateRandomArray(maxSize, maxValue);
int[] arr1 = SortModel.copyArray(randomArr);
int[] arr2 = SortModel.copyArray(randomArr);
insertionSort(arr1);
SortModel.comparator(arr2);
if (!SortModel.isEqual(arr1, arr2)) {
System.out.println("錯(cuò)誤: " + Arrays.toString(randomArr));
System.out.println("待測(cè)方法結(jié)果：" + Arrays.toString(arr1));
System.out.println("正確方法結(jié)果：" + Arrays.toString(arr2));
break;
}
}
}
}
實(shí)例6
理解遞歸行為，以及遞歸行為事件復(fù)雜度的估算
master公式的使用
T(N) = aT(N/b) + O(N^d)* 滿足master此形式的，都可以使用下面的計(jì)算方法計(jì)算時(shí)間復(fù)雜度
log(b,a) > d ---> 復(fù)雜度為O(N^log(b,a))
log(b,a) = d ---> 復(fù)雜度為O(N^d * logN)
log(b,a) < d ---> 復(fù)雜度為O(N^d)
ps: log(b, a) 表示以b 為底
補(bǔ)充閱讀：www.gocalf.com/blog/algorithm-complexity-and-mastertheorem.html
實(shí)例7
歸并排序
分治思想
左邊部分排序?yàn)橛行?/p>
右半部分排序?yàn)橛行?/p>
采用外排方式，合并兩個(gè)有序部分到一個(gè)臨時(shí)數(shù)組
復(fù)制回寫到原數(shù)組
import cn.zqtao.learn.model.SortModel;
import java.util.Arrays;
/**
* @description: 歸并排序
* <p>
* 分治思想
* <p>
* 左半部分排序
* 右半部分排序
* <p>
* 采用外排方式，合并兩個(gè)有序部分到一個(gè)臨時(shí)數(shù)組
* <p>
* 復(fù)制回原數(shù)組
* @version: 1.0
*/
public class Code_03_MergerSort {
public static void mergerSort(int[] arr) {
if (arr == null || arr.length < 2)
return;
sortProcess(arr, 0, arr.length - 1);
// System.out.println(Arrays.toString(arr));
}
public static void sortProcess(int[] arr, int L, int R) {
if (L == R)
return;
int mid = L + ((R - L) >> 1); // 等同于 (L + R) / 2
sortProcess(arr, L, mid);
sortProcess(arr, mid + 1, R);
merger(arr, L, mid, R); // O(N)
// T(N) = 2 T(N/2) + O(N) 符合master公式
// 所以時(shí)間復(fù)雜度： O(N * logN)
// 空間復(fù)雜度：O(N) 臨時(shí)輔助數(shù)組
}
// 合并兩個(gè)有序部分
private static void merger(int[] arr, int L, int mid, int R) {
// 輔助數(shù)組
int[] help = new int[R - L + 1];
int i = 0;
// 雙指針，分別指向第一個(gè)有序部分第一個(gè)數(shù)位置，第二個(gè)有序部分第一個(gè)數(shù)位置
int p1 = L;
int p2 = mid + 1;
// 外排方式選填進(jìn)入臨時(shí)輔助數(shù)組的數(shù), 當(dāng)兩個(gè)指針任意一個(gè)越界時(shí)跳出
while (p1 <= mid && p2 <= R) {
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
// 有且只有一個(gè)越界
while (p1 <= mid)
help[i++] = arr[p1++];
while (p2 <= R)
help[i++] = arr[p2++];
// 回寫到原數(shù)組
for (int j = 0; j < help.length; j++) {
arr[L + j] = help[j];
}
}
public static void main(String[] args) {
int testTime = 5000;
int maxSize = 10;
int maxValue = 100;
for (int i = 0; i < testTime; i++) {
int[] randomArr = SortModel.generateRandomArray(maxSize, maxValue);
int[] arr1 = SortModel.copyArray(randomArr);
int[] arr2 = SortModel.copyArray(randomArr);
mergerSort(arr1);
SortModel.comparator(arr2);
if (!SortModel.isEqual(arr1, arr2)) {
System.out.println("錯(cuò)誤: " + Arrays.toString(randomArr));
System.out.println("待測(cè)方法結(jié)果：" + Arrays.toString(arr1));
System.out.println("正確方法結(jié)果：" + Arrays.toString(arr2));
break;
}
}
}
}
時(shí)間復(fù)雜度： O(N * logN)
空間復(fù)雜度：O(N) 臨時(shí)輔助數(shù)組
實(shí)例8
小和問題和逆序?qū)栴}
小和問題
在一個(gè)數(shù)組中，每一個(gè)數(shù)左邊比當(dāng)前數(shù)小的數(shù)累加起來，叫做這個(gè)數(shù)組的小和。求一個(gè)數(shù)組 的小和。
例子： [1,3,4,2,5] 1左邊比1小的數(shù)，沒有； 3左邊比3小的數(shù)，1； 4左邊比4小的數(shù)，1、3； 2左邊比2小的數(shù)，1； 5左邊比5小的數(shù)，1、3、4、2； 所以小和為1+1+3+1+1+3+4+2=16
逆序?qū)栴} 在一個(gè)數(shù)組中，左邊的數(shù)如果比右邊的數(shù)大，則折兩個(gè)數(shù)構(gòu)成一個(gè)逆序?qū)?，?qǐng)打印所有逆序 對(duì)。
小和問題
import cn.zqtao.learn.model.SortModel;
import java.util.Arrays;
/**
* @description: 小和問題
* <p>
* 小和問題
* 在一個(gè)數(shù)組中，每一個(gè)數(shù)左邊比當(dāng)前數(shù)小的數(shù)累加起來，叫做這個(gè)數(shù)組的小和。求一個(gè)數(shù)組 的小和。
* 例子：
* [1,3,4,2,5]
* 1左邊比1小的數(shù)，沒有；
* 3左邊比3小的數(shù)，1；
* 4左邊比4小的數(shù)，1、3；
* 2左邊比2小的數(shù)，1；
* 5左邊比5小的數(shù)，1、3、4、2；
* 所以小和為1+1+3+1+1+3+4+2=16
* @version: 1.0
*/
public class Code_04_SmallSum {
public static int smallSum(int[] arr) {
if (arr == null || arr.length < 2) return 0;
return mergesort(arr, 0, arr.length - 1);
}
public static int mergesort(int[] arr, int L, int R) {
if (L == R) return 0;
int mid = L + ((R - L) >> 1);
return mergesort(arr, L, mid) +
mergesort(arr, mid + 1, R) +
merge(arr, L, mid, R);
//左邊產(chǎn)生的小和+右邊產(chǎn)生的小和+合并產(chǎn)生的小和就是整個(gè)數(shù)組的小和
}
public static int merge(int[] arr, int L, int mid, int R) {
// 輔助數(shù)組
int[] help = new int[R - L + 1];
int i = 0;
// 雙指針
int p1 = L;
int p2 = mid + 1;
int res = 0;
while (p1 <= mid && p2 <= R) {
// 左邊小于右邊，左邊數(shù) * 右邊比左邊大的數(shù)的個(gè)數(shù)，因?yàn)橐呀?jīng)使用歸并排序進(jìn)行了排序
// 所以右邊剩下的數(shù)也比左邊數(shù)大
// 如左邊 1 3
// 右邊 2 5 6
// 1 < 2 ,此時(shí)右邊數(shù)，5 6 一定都比1大， 則 小和結(jié)果是 1 * 3
res = arr[p1] < arr[p2] ? arr[p1] * (R - p2 + 1) : 0;
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= mid)
help[i++] = arr[p1++];
while (p2 <= R)
help[i++] = arr[p2++];
for (i = 0; i < help.length; i++)
arr[L + i] = help[i];
return res;
}
// for test 寫一個(gè)實(shí)現(xiàn)簡單，絕對(duì)正確但是時(shí)間復(fù)雜度高的算法
public static int comparator(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
int res = 0;
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
res += arr[j] < arr[i] ? arr[j] : 0;
}
}
return res;
}
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[] randomArr = SortModel.generateRandomArray(maxSize, maxValue);
int[] arr1 = SortModel.copyArray(randomArr);
int[] arr2 = SortModel.copyArray(randomArr);
if (!SortModel.isEqual(arr1, arr2)) {
succeed = false;
System.out.println("錯(cuò)誤: " + Arrays.toString(randomArr));
System.out.println("待測(cè)方法結(jié)果：" + Arrays.toString(arr1));
System.out.println("正確方法結(jié)果：" + Arrays.toString(arr2));
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
}
}
逆序?qū)?/p>
import java.util.Arrays;
import java.util.Scanner;
/**
* @description: 逆序?qū)栴}
* 在一個(gè)數(shù)組中，左邊的數(shù)如果比右邊的數(shù)大，則兩個(gè)數(shù)構(gòu)成一個(gè)逆序?qū)?，?qǐng)打印所有逆序?qū)? * @version: 1.0
*/
public class Code_05_InvertedNum {
public static void invertedNum(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);
// 打印左邊逆序?qū)? mergeSort(arr, L, mid);
// 打印右邊逆序?qū)? mergeSort(arr, mid + 1, R);
// 打印合并后的逆序?qū)? merge(arr, L, mid, R);
}
public static void merge(int[] arr, int L, int mid, int R) {
// 輔助數(shù)組
int[] help = new int[R - L + 1];
int i = 0;
int p1 = L;
int p2 = mid + 1;
while (p1 <= mid && p2 <= R) {
if (arr[p1] > arr[p2]) {
for (int j = p2; j <= R; j++) {
System.out.println("逆序?qū)Γ? + arr[p1] + "--" + arr[j]);
}
}
help[i++] = arr[p1] > arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= mid)
help[i++] = arr[p1++];
while (p2 <= R)
help[i++] = arr[p2++];
for (i = 0; i < help.length; i++)
arr[L + i] = help[i];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String[] str = sc.nextLine().split(",");
int[] num = new int[str.length];
for (int i = 0; i < str.length; i++) {
num[i] = Integer.parseInt(str[i]);
}
invertedNum(num);
}
sc.close();
}
}
以上都是算法課程學(xué)習(xí)總結(jié)
