前言：
📫 作者簡介：小明java問道之路，專注于研究計算機底層的部落客，就職于金融公司後端進階工程師，擅長交易領域的高安全/可用/并發/性能的設計和架構📫
🏆 Java領域新星創作者、阿裡雲專家部落客、華為雲享專家🏆
🔥 如果此文還不錯的話，還請👍關注、點贊、收藏三連支援👍一下部落客哦
本文導讀：本文介紹了學習算法和資料結構的方法和準備工作，介紹了學習算法的一些必要的專業名詞，時間複雜度、空間複雜度的代碼案例
一、訓練準備-怎麼學？學到什麼程度？
1、怎麼學？
第一遍：讀題和思考5-15分鐘，如果有思路的話自己開始做和寫代碼（思考所有的可能解法）；
如果沒思路看題解，前提是讀題思考15分鐘（了解題目的意思），看題解默寫背誦（思考所有的可能解法）、熟練（分析每種解法的思路），然後開始自己寫（閉卷）
第二遍：默寫程式、調試（先在頭腦裡面調試，實在不行再在編譯器裡調試），這一遍一定要弄會，會寫，哪怕時間長（刻意練習、分解—建構知識樹、知識模型）
第三遍：隔一天再寫一遍程式，思考那裡寫錯了，為了記憶
第四遍：一周後再寫一遍，思考和其他的知識模型的關聯，建立知識模型！
第五遍：面試前寫一遍，複習
2、學到什麼程度？
可以構件知識樹（知識模型、思維導圖），做過的題有多種解法，講出來舉一反三
二、複雜度原理
衡量代碼的好壞，包括兩個非常重要的名額：1.運作時間；2.占用空間。衡量标準有個度就是時間複雜度和空間複雜度
時間複雜度：算法的時間複雜度表示為，若存在函數 f（n），使得當n趨近于無窮大時，T（n）/ f（n）的極限值為不等于零的常數，則稱 f（n）是T（n）的同數量級函數。記作 T（n）= O（f（n）），稱O（f（n）） 為算法的漸進時間複雜度，簡稱時間複雜度。
空間複雜度：算法的空間複雜度通過計算算法所需的存儲空間實作，算法空間複雜度的計算公式記作：S(n)=O(f(n))，其中，n為問題的規模，f(n)為語句關于n所占存儲空間的函數。
如何推導出時間複雜度呢，有如下幾個原則：
1、如果運作時間是常數量級，用常數1表示；
2、隻保留時間函數中的最高階項；
3、如果最高階項存在，則省去最高階項前面的系數。
如何影響空間複雜度的三個方面：
一個算法在計算機存儲器上所占用的存儲空間，包括
1、存儲算法本身所占用的存儲空間
2、算法的輸入輸出資料所占用的存儲空間
3、算法在運作過程中臨時占用的存儲空間
三、複雜度算法分析
（一）幾種時間複雜度的代碼示例
O(1) 算法
一種算法的運算次數與資料規模無關，那麼它的時間複雜度是常數級别的，寫成 O(1)，雜湊演算法就是典型的O(1)時間複雜度，無論資料規模多大，都可以在一次計算後找到目标。
int fun(int key) {
return -key;
} O(logn) 算法
時間複雜度O(logn)對數階，當資料增大n倍時，耗時增大logn倍，二分查找就是O(logn)的算法，每次排除一半的可能
int fun(int a[], int key) {
int low = 0;
int high = a.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (a[mid] > key) high = mid - 1;
else if (a[mid] < key) low = mid + 1;
else return mid;
}
return -1;
} O(n) 算法
線性階，就代表資料量增大幾倍，耗時也增大幾倍，比如常見的周遊算法
void fun(int i) {
for (int a = 0; a < i; a++)
} O(nlogn)算法
線性對數，就是n乘以logn（周遊的同時内部可以排除一半資料），當資料增大256，耗時增大256*8=2048倍。這個複雜度高于線性低于平方。歸并排序就是O(nlogn)的時間複雜度。
public void mergeSort(int[] arr, int p, int q) {
if (p >= q) return;
int mid = (p + q) / 2;
mergeSort(arr, p, mid);
mergeSort(arr, mid + 1, q);
merge(arr, p, mid, q);
}
private void merge(int[] arr, int p, int mid, int q) {
int[] temp = new int[arr.length];
int i = p, j = mid + 1, iter = p;
while (i <= mid && j <= q) {
if (arr[i] <= arr[j]) temp[iter++] = arr[i++];
else temp[iter++] = arr[j++];
}
while (i <= mid) {
temp[iter++] = arr[i++];
}
while (j <= q) {
temp[iter++] = arr[j++];
}
for (int t = p; t <= q; t++) arr[t] = temp[t];
} O(n²)算法
void fun(int i) {
for (int a = 0; a < i; a++)
for (int b = a; a < i; a++)
} 對比O(n³) 算法、 O(n²)算法、O(nlogn) 算法、O(n) 算法、O(logn) 算法
（二）幾種空間複雜度的代碼示例
常量空間
類似于時間複雜度 O(1)，當算法的存儲空間大小固定，和輸入規模沒有直接的關系時，空間複雜度記作O(1)
int a = 0; 線性空間
當算法配置設定的空間是一個線性的集合（如數組），并且集合大小和輸入規模 n 成正比時，空間複雜度記作 O(n)
int[] a = new int[n]; 二維空間
當算法配置設定的空間是一個二維數組集合，并且集合的長度和寬度都與輸入規模 n 成正比時，空間複雜度記作 O(n^2)
int[][] arr = new int[i][j]; void fun(int i) {
fun(i);
}