什麼是數據結構，又什麼是算法
百度百科釋義：算法（Algorithm）是指解題方案的準確而完整的描述，是一系列解決問題的清晰指令，算法代表著用系統的方法描述解決問題的策略機制...一個算法的優劣可以用空間複雜度與時間複雜度來衡量。
懂了沒？其實我也懵逼。這些定義都很抽象，對理解這兩個概念並沒有實質性的幫助，你要是深究反而容易陷進誤區
表達從簡單開始~
形象地說，數據結構就是指存儲數據的結構。算法就是操作數據的方法。
圖書館你總去過吧，圖書館員為了方便讀者查找書籍，會把書本分門別類的放好並按規律編號。這裡排放規律的書籍其實就是一種數據結構。
那你怎麼來找書呢？是一本一本的找；根據 人文與社科，電子與信息技術，城市規劃與建設 書館尋找；還是到電腦搜索書名再拿著得到的編號找... 這就是 查找的算法
數據結構和算法又為什麼常常要一起講
那是因為算法只能作用於特定的數據結構，而數據結構又會根據自身特點推演出特定的算法。
比如剛才的例子：
- 按規律編號的書籍，可以一本一本找；分書館找；按索引找；
- 亂堆連放的書籍，你就只能一本一本找了
數據結構是隻是種堆放數據的方式，數據結構與算法研究的是如何快和省的問題，你不根據數據結構的規律特點談算法是沒用的。
時間/空間複雜度分析又是什麼
剛才我們說到：數據結構與算法研究的是如何快和省地解決問題 —— 那如何才算快，怎樣才是省呢。
所以如何衡量算法的 執行效率，使用空間 是個很重要的標準 —— 這就需要我們的 時間複雜度分析和空間複雜度分析
它有多重要呢 —— 我感覺這就是數據結構與算法課程裡的半壁江山，之後說的具體結構和算法都是圍著這個標準轉的
為什麼需要時間/空間複雜度分析
算法效率的度量方法內有一種就叫事後統計方法，說白了就是：寫個單元測試跑一遍算法，就消耗多少內存，多少時間。
很簡單直接。可問題是這個單元測試
- 在Intel Core i9、Intel Core i3 處理器上跑出的性能不一樣
- 數據量大、數據量小跑出來的性能也不一樣
這不就是擺明挖坑給自己，就看什麼時候跳嘛。
所以我們需要一個不依賴具體測試環境、具體數據，就可以粗略估計算法執行效率的方法。
那具體是個怎樣的方法呢
大 O 複雜度表示法
可有可無的解釋：大 O 時間複雜度表示法表示代碼執行時間隨數據規模增長的變化趨勢，也叫漸進時間複雜度，簡稱時間複雜度。
我們從一段普通的java代碼說起~
1 int i;
2 for( i=0; i < n; i++ ){
3 sum = sum + i;
4 }
執行情況：
- 第 1 行，執行了一遍；
- 第 2、3 行，執行了n遍；
所以這段普通的java代碼執行次數是：2n+1
我們假設每行語句的執行一遍的時間是一個單位時間（unit_time）。所以整段代碼總的執行時間:
T(n) = (2n+1)*unit_time
儘管我們不知道 unit_time 的具體值，但是通過公式，我們知道所有代碼的執行時間 T(n) 與每行代碼的執行次數 n 成正比。
因此我們可以引出這麼條公式：T(n) = O(f(n)) (不用記，繼續往下看)，於是普通的java代碼執行時間會演變成：
T(n) = O(2n+1)
然後時間複雜度分析，只關注執行次數最多的那段代碼，且忽略係數、常量、對數的“底”。於是最後普通的java代碼的時間複雜度是：O(n)
時間複雜度分析，說到這裡基本概念就說完。撒花~~ 不過還有兩個容易產生誤會的點，需要三申五令：
1. 只關注執行次數最多的那段代碼
1 int i, j, q, n = 100;
2 for ( q=0; q < n; q++ ) {
3 printf(“I love u\\n”);
4 }
5
6 for( i=0; i < n; i++ ){
7 printf(“I love u”);
8 for( j=0; j < n; j++ ){
9 printf(“ three thousand times\\n”);
10 }
11 }
執行情況：
- 第 1 行，執行了一遍；
- 第 2、3 行，執行了n遍；
- 第 6、7 行，執行了n遍；
- 第 8、9 行，執行了nn遍； 所以這段代碼執行次數是：1+n+n+(nn),因為：
時間複雜度分析，只關注執行次數最多的那段代碼，且忽略係數、常量、對數的“底”。
所以最後的時間複雜度為：O(n2) ...(n的2次方)
2. 關注代碼執行次數
時間複雜度分析，我們本質分析的是什麼？—— 時間嗎？不，我們看的是代碼執行次數。
假設每行語句的執行一遍的時間是一個單位時間（unit_time）—— 是因為有了這個假設，我們才把次數換單位時間，從而推導出O(n)
為什麼專門提這一點呢?我們舉個例子：
1 int i=0;
2 while (i < n) {
3 i = i * 2;
4 }
如果你說是O(n),恭喜，我賞你一丈紅。答錯了！認真看我推導... 我們假設 x 為執行次數，那麼上面代碼 x 和 n 的關係為：
所以執行次數與 n 的關係為：
由於 一次執行次數等於一個單位時間，且對數的“底”。所以最後的時間複雜度為
空間複雜度分析
空間複雜度分析和時間複雜度分析類似，你只需要把 一次執行次數等於一個單位內存把大 O 複雜度表示法重推一遍就會啦~
結語
複雜度分析並不難，關鍵在於多練。從低階到高階有：O(1)、O(logn)、O(n)、O(nlogn)、O(n2)。
雖然 複雜度分析還有最好、最壞、均攤(平均)複雜度分析。 但個人感覺 你掌握上面的複雜度分析，再加個均攤複雜度分析。學習工作就夠用了。
而均攤複雜度分析,我的理解是
多少種情況 被 各情況的“時間複雜度之和”相除
閱讀更多 銳玩道 的文章
