一文講透演算法中的時間複雜度和空間複雜度計算方式
前言
作為一名「程式猿」，大家應該都聽過這麼一句話：程式=數據結構+演算法。
這句話是由瑞士電腦科學家尼古拉斯·沃斯（Niklaus Wirth）在 1984 年獲得圖靈獎時說的一句話，這位大佬還以這句話為名出了一本書《Algorithms + Data Structures=Programs》，從此這句話就成為了大家耳熟能詳的一句名言。
隨著時間的推移，不管這句話是不是非常準確，但至少能說明數據結構與演算法對程式來說是非常核心的基礎，如果我們想要寫出更多優秀優雅的程式碼，那麼數據結構與演算法是必須要掌握好的。
為什麼要學習演算法
很多人可能覺得，我不會演算法，程式碼一樣寫得很”溜”，演算法這東西似乎用處不大。現在互聯網的發達，我們想要什麼幾乎都可以在網上找到現成的，各種框架功能十分強大，似乎看起來確實不用演算法也可以寫出「好程式碼」。然而假如我們不懂演算法，比如項目中用到了排序，我們如何評估程式碼的執行效率？再比如最常用的 ArrayList 和 LinkedList，我們該如何選擇，又比如說我們需要去集合中找某一個數，又該如何寫出性能優秀的程式碼呢？
同樣的程式碼，如何判斷誰的程式碼是優秀的程式碼？可讀性，可擴展性，健壯性可能都可以用來判定，然而這些東西我覺得並不能直接體現出你程式碼的優秀，因為對用戶而言，訪問你的程式碼響應速度快那就是優秀的程式碼，相反，動輒響應幾秒甚至更長時間的介面，恐怕就算你可讀性再好，再健壯也稱不上是好程式碼。
所以說一段程式碼是否優秀，最直接的判斷標準就是性能，而如果要寫出高性能的程式碼，那麼就必須要了解演算法，而且拋開這個因素，但凡不想一輩子都寫 CRUD 程式碼的，也需要去了解演算法，我們使用的很多框架和中間件底層都有數據結構和演算法的身影，學好演算法對我們源碼閱讀時理解其設計思想也是大有裨益的。
要說功利性的目的，那就是面試，目前很多大廠的面試，演算法基本必面，所以想進大廠的話，咱們也得好好學學演算法。
演算法難學嗎
提到演算法，很多人的第一反應就是太難學了，學不會，或者說經常是看完就忘了，但是其實對於我們一個普通的開發者而言，因為並不需要我們去發明演算法，我們需要的僅僅只是去靈活的運用演算法，所以並不需要非常紮實的數據基礎，當然基本的數學常識還是要有的。
如果說需要去發明設計一款演算法，那就要去推導去證明演算法的可行性，這種是需要具有非常紮實的數學基礎的，一般人確實無法做到，然而我們普通程式設計師口中提到演算法無非是二分查找法，哈希演算法等，高級一點的就還有回溯，貪心，動態規劃等等，這些所謂的演算法都是已經有現成的公式了，我們要做的無非就是理解它，然後靈活的運用它。這就和我們以前學習數學公式一樣，給你一個公式，然後你去做題，做題的過程其實就是去靈活的運用這個公式。
演算法也是同理，都是有特定方法和特定思路的，我們也並不需要去推導證明這種方式為什麼可行，所以學習演算法沒有其他訣竅，就是先理解思路，然後多練，等熟練了，自然就可以靈活運用了，也不會說學了立刻就忘了。學完就忘無非兩個原因，一是沒理解，而是沒有練習鞏固。
複雜度分析
數據結構與演算法經常是放在一起講，這兩者是沒辦法獨立的，因為演算法是為了達到某種目的的一種實現方式，而數據結構是一種載體，也就是說演算法必須依賴數據結構這種載體，否則就是空談。換句話說：數據結構是為演算法服務的，而演算法又需要作用在特定的數據結構之上。
一個演算法到底好不好，我們如何去評價？前面我們提到了，你的程式碼好不好，最直觀的就是看響應速度，演算法也一樣，同樣實現一個目的（比如說排序），誰的演算法速度快，我們就可以認為誰的演算法更優，如果說兩種演算法實現的速度差不多，那麼我們還可以去評價演算法所佔用的空間，誰佔用的空間少，那麼就可以認為誰的演算法更優，這就是演算法的基礎：時間複雜度和空間複雜度。
學習演算法之前，我們必須要學會如何分析時間複雜度和空間複雜度（也就是「快」和「省」），否則自己寫出來的演算法自己都不知道演算法的效率。
時間複雜度大 O表示法
接觸過演算法的都知道，演算法的時間複雜度是用大寫的「O」來表示的，比如：O(1)，O(n)，O(logn)，O(nlogn)，O(n²) 等等。
時間複雜度的全稱是漸進時間複雜度，表示演算法的執行時間與數據規模之間的增長關係，上面的這種時間複雜度表示法並不能真正反應一個演算法的執行時間，反應的只是一個趨勢，所以我們在分析複雜度的時候要關注「變」，忽略「不變」。
變指的是變數，也就是一段程式碼的執行時間是隨著變數的變化而變化的，而不變指的是常量，也就是不論我的變數如何改變，執行時間都不會改變。
接下來我們就實際的來分析下常用時間複雜度的例子來練習一下。
O(1) 常數階
0(1) 複雜度演算法也稱之為常數階演算法。這裡的 1 是用來代指常量，也就是說這個演算法的效率是固定的，無論你的數據量如何變化，效率都一樣，這種複雜度也是最優的一種演算法。
public static void print(int n){
int a = 1;
int b = 2;
int c = 3;
int sum = a + b + c;
System.out.println(sum);
}
上面的示例中不論有多少行程式碼，時間複雜度都是屬於常數階。換言之：只要程式碼不存在循環，遞歸等循環類調用，不論程式碼有多少行，其複雜度都是常數階。
O(n) 線性階
O(n) 複雜度演算法也稱之為線性階。比如下面這個示例我們應該怎麼分析複雜度呢？
public static void print1(int n){
int a = 0;
for (int i=0;i<n;i++){
System.out.println(i);
}
}
前面常量階沒分析是因為常量階比較容易理解，接下來我們就以線性階這個為例子來分析下具體是怎麼得到的。
我們假設每一行程式碼的執行時間是 T，那麼上面這段程式碼的執行複雜度是多少呢？
答案很明顯，那就是 T+n*T，也就是 (n+1)T，而在演算法中有一個原則，那就是常量可以被忽略，所以就得到了 nT，換成大 O 表示法就是 O(n)。
這只是一個簡略的計算過程，大家也不用較真說每行程式碼執行時間可能不一樣之類的，也不要較真說 for 循環佔用了一行，下面的大括弧也佔用了一行，如果要較真這個，那我建議可以去想一下 1=1 為什麼等於 2。
演算法中的複雜度反應的只是一個趨勢，這裡 O(n) 反應的就是一個趨勢，也就是隨著 n 的變化，演算法的執行時間是會降低的。
O(n²) 平方階
知道了上面的線性階，那麼平方階就很好理解了，雙層循環就是平方階，同理，三次循環就是立方階，k 次循環就是 k 次方階。
O(logn) 對數階
O(logn) 也稱之為對數階，對數階也很常見，像二分查找，二叉樹之類的問題中會見到比較多的對數階複雜度，但是對數階也是比較難理解的一種演算法複雜度。
下面我們還是來看一個例子：
public static void print2(int n){
int i=1;
while (i <= n) {
i = i * 2;
}
}
這段程式碼又該如何分析複雜度呢？這段程式碼最關鍵就是要分析出 while 循環中到底循環了多少次，我們觀察這個循環，發現 i 並不是逐一遞增，而是不斷的翻倍：1->2->4->8->16->32->64 一直到等於 n 為止才會結束，所以我們得到了這樣的一個公式：2^x=n。
也就是我們只要計算出 x 的值，就得到了循環次數，而根據高中的數學知識我們可以得到 x=log2n（2 在下面，是底數，試了幾種方法都打不出來，放棄了），所以根據上麵線性階的分析方法，我們省略常量，就得到了示例中的演算法複雜度為 O(log2n)。
同樣的分析方式，下面的例子，我們可以很快的分析出複雜度就為 O(log3n)：
int i=1;
while (i <= n) {
i = i * 3;
}
上面得到的 log3n 我們可以再做進一步的轉換：log3n=log32 * log2n，而 log32（注意這幾個地方的 3 是底數，在下面） 是一個常量，常量可以省略，所以也就得到了：O(log3n)=O(log2n)。同樣的道理，不論底數是多少，其實最終都可以轉化成和 O(log2n) 相等，正因為如此，為了方便，我們演算法中通常就會省略底數，直接寫作 O(logn)。
上面的數學公式大家如果忘了或者看不懂也沒關係，只要記住不論對數的底數是多少，我們都算作 O(logn)，而對於一個演算法的複雜度是否是對數階，還有一個簡易的判斷方法：當循環中下標以指定倍數形式衰減，那麼這就是一個對數階。
O(nlogn) 線性對數階
如果理解了上面的對數階，那麼這種線性對數階就非常好理解了，只需要在對數階的演算法中再嵌一層循環就是線性對數階：
int i=1;
for (int j=1;j<=n;j++){
while (i <= n) {
i = i * 2;
}
}
分析了前面這些最常用的時間複雜度，其實我們可以得到以下規律：
- 只要是常量級別，不論多大，效率都是一樣的（如：常量階複雜度例子）。
- 分析一段程式碼的時間複雜度，只需要分析執行次數最多的一段程式碼（如：所以例子中我們只分析了循環體中程式碼執行次數）。
- 嵌套程式碼的複雜度等於嵌套內外程式碼複雜度的乘積（如：分析線性對數階複雜度例子）。
其他複雜度
除了上面常用的複雜度之外，另外還有指數階，階層階，根號階等，這些接觸的相對會較少，我們就不特意做分析了，如果大家感興趣的話，可以自己去了解下。
組合式複雜度分析
前面我們分析的都是只有一段程式碼比較複雜的情況下得到的複雜度結果，那麼假如我一個演算法中，有多段程式碼都比較複雜呢？這時候複雜度該如何分析？
取最大複雜度作為整個演算法複雜度
我們先看下面這個例子：
public static void print1(int n){
for (int i=0;i<1000;i++){
System.out.println(i);
}
for (int j=0;j<n;j++){
System.out.println(j);
}
for (int p=0;p<n;p++){
for (int q=0;q<n;q++){
System.out.println(p+q);
}
}
}
這個例子中有三個循環，首先第一個，是一個常量，那麼根據前面的結論，不論這個常量是多大，都屬於常量級，所以第一個循環中的複雜度為 O(1)，第二個和第三個循環我們前面也分析過，複雜度分別為 O(n) 和 O(n²)。
也就是這一段程式碼中有三段程式碼產生了三種不同複雜度，而且這三個複雜度可以很明顯得到的大小關係為：O(1)<O(n)<O(n²)，像這種在同一個演算法中有明確大小關係的，我們就可以直接取最大值作為這個演算法的複雜度，所以這個例子中演算法的複雜度就是 O(n²)。
取多個複雜度之和作為整個演算法複雜度
接下來我們再來看一個例子：
public static void print2(int m,int n){
for (int i=0;i<1000;i++){
System.out.println(i);
}
for (int j=0;j<m;j++){
System.out.println(j);
}
for (int k=0;k<n;k++){
System.out.println(k);
}
}
這個例子我們同樣對三段循環分別分析可以分別得到如下複雜度：O(1)，O(m)，O(n)。這時候我們只能知道 O(1) 最小可以忽略，但是後面兩個無法卻無法確定大小，所以這時候我們需要取兩段循環複雜度之和來作為演算法的複雜度，所以可以得到這個例子的演算法複雜度為：O(m+n)。
時間複雜度類型
上面分析的時間複雜度都是比較簡單的，實際演算法中可能會比示例中複雜的多，而且我們示例中只要是循環都是無腦循環，也就是一定從頭循環到尾，然而實際中我們有時候並不需要從頭循環到尾，可能中途就會結束循環，所以我們根據實際情況，又可以將時間複雜度從以下四個方面來進一步分析：
- 最好時間複雜度
- 最壞時間複雜度
- 平均時間複雜度
- 均攤時間複雜度
這四種類型的時間複雜度在這裡只會介紹前面三種，因為第四種比較複雜，而且使用場景也非常有限，而且對於這四種複雜度的分析，大家也作為了解就可以，不敢興趣的朋友們可以跳過這一小部分，因為在絕大部分情況我們只需要分析最壞複雜度就行，也就是假設循環全部執行完畢場景下的時間複雜度。
最好時間複雜度
我們通過一個例子來理解下最好時間複雜度：
public static int findEle(int[] arr,int val){
if (null == arr || arr.length == 0){
return -1;
}
for (int i=0;i<arr.length;i++){
if (arr[i] == val){
return i;
}
}
return -1;
}
這個方法就是在一個指定數組中找到指定元素的下標，找不到就返回 -1，這個方法比較簡單，應該比較好理解。
注意這個方法中的循環體，如果找到元素，那麼就直接返回，這就會有一個現象，那就是我這個循環體到底會循環多少次是不確定的，可能是 1 次，也可能是 n（假設數組的長度） 次，所以假如我們要找的元素就在數組中的第一個位置，那麼我循環一次就找到了，這個演算法的複雜度就是 O(1)，這就是最好情況時間複雜度。
最壞時間複雜度
理解了最好時間複雜度，那麼最壞時間複雜度也很好理解了，那就是數組中不存在我要找到元素，或者說最後一個值才是我要找的元素，那麼這樣我就必須循環完整個數組，那麼時間複雜度就是 O(n)，這也就是最壞時間複雜度。
平均時間複雜度
最好時間複雜度和最壞時間複雜度畢竟只有特殊情況才會發生，概率還是相對較小，所以我們很容易就想到我們也需要有一個平均時間複雜度。
我們簡單的來分析一下，為了便於分析，我們假設一個元素在數組和不在數組中的概率都為 1/2，然後假如在數組在，那麼又假設元素出現在每個位置的概率也是一樣的，也就是每個位置出現元素的概率為： 1/n。
所以最終得到的平均時間複雜度應該等於元素在數組中和元素不在數組中兩種情況相加。
- 元素在數組中的複雜度
因為元素在數組中的概率為 1/2，然後在每個位置出現的概率也為 1/n。假如元素出現在第一個位置，複雜度為 1*(1/2n)；假如元素出現在第二個位置，複雜度為 2 * (1/2n)，最終得到當前場景下時間複雜度為：1*(1/2n) + 2 * (1/2n) + ... + n*(1/2n)=(n+1)/4。
- 元素不在數組中的複雜度
前面已經假定了元素不在數組中的概率為 1/2，所以當前場景下的時間複雜度為：n * (1/2)，因為元素不在數組中，那麼這個演算法必然會將整個循環執行完畢，也就循環是 n 次。
最後我們把兩種情況的複雜度之和相加就得到了平均時間複雜度：(n+1)/4 + n/2 = (3n+1)/4，最終我們將常數類的係數忽略掉，就得到了平均時間複雜度為 O(n)。
均攤時間複雜度
均攤時間複雜度的演算法需要使用攤還分析法，計算方式相對有點複雜，而且使用場景很有限，本文就不做過多介紹了。
空間複雜度
空間複雜度全稱就是漸進空間複雜度，用來表示演算法的存儲空間與數據規模之間的增長關係。和時間複雜度一樣，空間複雜度也是用大 O 進行表示。
其實學會了分析時間複雜度，那麼空間複雜度的分析就簡單了，主要就看我們在一個演算法當中到底有沒有使用到了額外的空間來進行存儲數據，然後判斷這個額外空間的大小會不會隨著 n 的變化而變化，從而得到空間複雜度。
我們來看一個給數組賦值例子，假設這就是一個演算法，我們可以來分析下這個演算法的空間複雜度：
public static void init(int n){
int a = 0;
int arr[] = new int[n];
for (int i=0;i<n;i++){
arr[i]=n;
}
}
一開始定義了一個變數，這裡需要空間，但是這是一個常量級的（不隨 n 的變化而變化），然後再定義了一個數組，數組的長度為 n，這裡數組也需要佔用空間，而且數組的空間是隨著 n 的變化而變化的，其餘程式碼沒有佔用額外空間，所以我們就可以認為上面示例中的空間複雜度為 O(n)。
對於演算法的空間複雜度也可以簡單的進行總結一下：
- 如果申請的是有限個數（常量）的變數，空間複雜度為
O(1)。 - 如果申請的是一維數組，隊列或者鏈表等，那麼空間複雜度為
O(n)。 - 如果申請的是二維數組，那麼空間複雜度為
O(n²)。 - 如果是在循環體中申請的數組等，可能就需要取嵌套的乘積來作為空間複雜度，這種就需要具體的進一步分析。
總結
本文主要講述了為什麼要學習演算法，也簡單減少了數據結構與演算法之間的關係，隨後主要介紹了演算法中的入門知識：時間複雜度和空間複雜度。想要學好演算法，必須要掌握如何分析一個演算法的時間複雜度和空間複雜度，只有自己會分析這兩個個衡量演算法主要性能的標準，才能更好的寫出性能優秀的演算法，同時我們也講到了最好時間複雜度，最壞時間複雜度，平均時間複雜度和均攤時間複雜度，不過這四種複雜度的計算方式大家作為了解即可，等實際確實需要使用到再來回顧也不遲。
