0、什么是算法的復雜度？
對于任何一個程序來說，都可以從三個方面進行分析，分別是 輸入、處理、輸出，也即 IPO（Input、Process、Output），這種分析方法對硬件和軟件程序都是適用的。
數(shù)據的來源（Input）：可以是硬件傳感器收集的，也可以是從網上爬取的...。數(shù)據的輸出（Output）：可以顯示在網頁上，安卓APP上，電子屏幕上...。而最重要的是程序處理，可以對數(shù)據進行簡單的處理，也可以對數(shù)據進行挖掘...。
就拿最簡單的 Hello World 程序來說，也是由這三方面組成的，輸出函數(shù)（處理）幫你處理輸入的 “Hello World” 字符串（輸入），然后再幫你將這些字符輸出顯示到控制臺上（輸出）。大到現(xiàn)在熱門的技術，物聯(lián)網、大數(shù)據，人工智能等，做的也無非都是上面三個方面內的事情，關于這些，讀者可以思考一下。
評價一個程序的復雜程度，關鍵也是看程序中處理數(shù)據的這部分，對數(shù)據處理就要用到算法了。什么？你說你沒有用過算法，其實從你編程開始的第一句 “Hello World” 就注定編程和算法分不開了，一個輸出函數(shù)背后也同樣有算法呀，只是你在使用算法的時候并沒有意識到你在用算法罷了（嘿嘿，就是這么神奇~）。
算法是一個程序的靈魂，就好比沒有蛋的泡面是沒有靈魂的一樣。一個好的算法可以有很多的應用，比如在美劇《硅谷》中，主角發(fā)明了一種壓縮算法，將它用在音樂、云存儲、視頻等方面都大獲成功。雖然故事是虛構的，但是在一方面也說明了算法的重要性。
分析一個算法的復雜度，也是在分析一個算法的好壞優(yōu)劣，簡單高效的算法才是我們應該追求的，而復雜低效的算法則是我們需要改進的。算法的復雜度包括 時間復雜度 和 空間復雜度，下面將用盡量少的概念來幫你搞懂這兩個度。
1、什么是算法的時間復雜度？
討論算法的時間復雜度，也是在討論程序使用該算法運行的時間。經常聽到身邊的同學說我的電腦好慢呀，打開個軟件都要一分多鐘，急死人了。這從算法的角度看，只能說電腦硬件比較差，不一定說程序寫的很垃圾（當然也有可能有程序的鍋），同樣的程序可能在別人配置高的電腦上打開就很快。所以你看單純從程序運行需要的時間長短上，并不能反映算法的優(yōu)劣，因為這和運行的設備也有很大關系（計算機計算主要用到的是 CPU 和 GPU）。
算法的時間復雜度并不能以具體的時間數(shù)值為單位（如1秒鐘，1分鐘等），那算法復雜度中的時間單位是什么呢？這個時間單位其實更像是程序中執(zhí)行的次數(shù)或者步驟數(shù)。
舉個栗子，當你忘記東西放哪里了，可能會把所有的抽屜都找一遍，假如你有 n 個抽屜，那么找完 n 個抽屜就可以找到你的東西了，每個抽屜都找了一遍，就找了 n 遍。算法的時間復雜度（運行時間）用大 O 表示（不需要關心大 O 表示法怎么來的，就是個名字），把你找東西的這個過程寫成程序，算法的時間復雜度就是 O(n)，是不是感覺算法其實就在我們中間。
在上面這個例子中，最好的情況是，當你找完第一個抽屜，你就找到你的東西了，這當然是最好的了，用大 O 表示法表示就是 O(1)，但是這樣的情況存在偶然性，并不能代表算法的復雜度；最壞的情況是，直到你找完最后一個抽屜，累的要死，你才找到你的東西，用大 O 表示法表示就是 O(n)。位于最壞和最好之間的情況是，當你找到中間一個抽屜時，你找到的你的東西了，用大 O 表示法表示就是 O(n/2)。
那么這三種情況，哪一種應該代表算法的時間復雜度呢？最好的情況畢竟是小概率事件，不具有普適性，肯定是不能代表算法真實的時間復雜度。平均的情況，確實在一定程度上可以反映出算法的時間復雜度，但是學過數(shù)學的我們知道，平均值容易受到極端值的影響（在評委打分時也經常是去掉最高分和最低分），所以平均情況也不是很合適。而最壞的情況卻可以給我們一種保證，我們心里也可以有一個預期，這個算法在最差的情況下表現(xiàn)如何（就像我們做事也常常考慮最壞的情況一樣），所以我們用最壞情況下的時間復雜度來衡量算法的時間復雜度。
對于大 O 括號內的參數(shù)（或者稱為操作數(shù)）的系數(shù)，往往被我們主動忽略，如一個計算出所需次數(shù)為 n/2 的算法，用大 O 表示法表示是 O(n)，而對于計算次數(shù)是個常數(shù)（如 1，5， 9）的算法，用大 O 表示法表示都是 O(1)，這點是需要我們注意一下的。為什么這樣做呢？因為對于計算次數(shù)是 n2/2 + n/2 + 5 這樣的算法，起決定作用的是 n，而不是 n 前面的系數(shù)，當 n 為無窮大時，n 前面系數(shù)的影響就微不足道了，最終這個算法的時間復雜度用大 O 表示法為 O(n2 + n)。
2、什么是算法的空間復雜度？
程序運行時肯定是要消耗空間資源的，寄存器、內存和磁盤等。輸入和輸出這兩部分占用空間是必需的，所以程序處理的空間指的是程序運行算法時所需的那部分空間。先來看個例子，交換兩個數(shù)的值，相信大家都做過吧，一般的方法是找一個中間變量存儲其中一個數(shù)的值，再讓一個數(shù)等于另一個數(shù)的值，另外一個數(shù)等于中間變量的值，就像下面的偽代碼這樣。
// 交換 a 和 b
temp = a
a = b
b = temp
棧這種數(shù)據結構，我都應該很熟悉，特點是先進后出（FILO），交換的這兩個數(shù)肯定都是要放在棧中的，但由于引入了中間變量實現(xiàn)，所以在程序棧中還要有中間變量的空間，一個變量占用一塊棧空間（想象一下），我們用一個格子來表示，就像下面這樣，中間變量也要占用一個格子（其實這個格子在其他棧中叫做 幀，如 Java虛擬機的本地方法棧和虛擬機棧，幀又是一種數(shù)據結構）。
因為這個值交換算法用到了中間變量，而中間變量又要占用一個格子，所以這個算法的空間復雜度用大 O 表示法表示就是 O(1)。
相比較而言，算法的空間復雜度比較簡單，所以我們在討論一個算法時，更多的是討論算法的時間復雜度。
3、一些常見的大 O 運行時間
- O(1)，如 y = x + 1，只需要一次計算便可得到結果。
- O(logn)，也稱為對數(shù)時間，如二分查找算法。
- O(n)，也稱為線性時間，如我們上面例子中的找東西，用的就是簡單查找算法。
- O(n*logn)，如快速排序算法。
- O(n2)，如選擇排序算法。
- O(n!)，如著名的旅行商問題。
這里提到的算法，將在后面的文章中討論，感興趣的小伙伴不妨先搜索了解一下。
上面幾種大 O 運行時間，反應在圖中如下（注意：圖中曲線并不一定從原點開始畫的，只需要知道算法運行時間的大概走勢就可以了）：
算法的速度，指的并不是時間，而是增速，反應的在圖中就是曲線的斜率，可以看到，隨著輸入的增加，有的算法所需要的時間越來長，也就是使用這種算法的程序會越來越慢。
4、小結
算法的復雜度和需要的時間、空間都有關系，我們更多談論的是算法的時間復雜度，算法的時間復雜度不是以秒為單位，算法運行的速度是從其增速的角度度量的，也即是輸入越多，算法運行的時間改變的快慢。一個好的算法應該是時間復雜度和空間復雜度都比較低，通俗的說就是花最少的時間和精力達到最好的效果，但是這兩樣往往是很難同時做到的，這就需要我們犧牲一樣來做到盡可能的更好。
——本文轉自我的微信公眾號《編程心路》。
