保姆級教學(xué)！徹底學(xué)會時間復(fù)雜度和空間復(fù)雜度
大家好呀，我是蛋蛋。
數(shù)據(jù)結(jié)構(gòu)與算法，作為編程界從入門到勸退的王者，是很多初學(xué)者心中神圣而想侵犯的村花兒，化身舔狗，費盡心思，舔到最后，我命油我不油天。
作為一名大學(xué)之前編程能力為零，以為計算機專業(yè)就是打游戲的咸魚，到參加 ACM 競賽，靠著劃水和抱大腿拿了幾塊金銀銅鐵牌的前 ACM 混子選手，想起之前瘋狂跪舔數(shù)據(jù)結(jié)構(gòu)和算法的日子，至今我扔能掬出一把辛酸淚。
為了讓臭寶們不再像我這樣當(dāng)個人這么難，我決定和大家一起學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法，我希望能用傻瓜的方式，由淺入深，從概念到實踐，一步一步的來，這個過程可能會很長，我希望在這個過程中你能喜歡上它，能發(fā)現(xiàn)它們冰冷外表下有趣的靈魂。
學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的第一課，我永遠(yuǎn)都選復(fù)雜度分析，在我看來，這是數(shù)據(jù)結(jié)構(gòu)與算法中最重要的知識點，且不接受任何反駁。
復(fù)雜度分析主要就是時間復(fù)雜度和空間復(fù)雜度，接下來的文章也主要圍繞這兩方面來講。廢話不多說，前排馬扎瓜子準(zhǔn)備好，蛋蛋小課堂正式接客
復(fù)雜度分析
剛剛我說過，在本蛋看來，復(fù)雜度分析是數(shù)據(jù)結(jié)構(gòu)和算法中最重要的知識點，毫不夸張的說，這就是數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)的核心所在。你學(xué)會了它你就入的了門，你學(xué)不會它，你就永遠(yuǎn)不知道門兒在哪。
為什么復(fù)雜度分析會這么重要？
這個就要從盤古開天辟地，呃，從數(shù)據(jù)結(jié)構(gòu)與算法的本身說起。
我平常白天做夢的時候，總是想著當(dāng)當(dāng)咸魚劃劃水就能賺大錢，最好就是能躺著，錢就直接砸到我腦闊上。數(shù)據(jù)結(jié)構(gòu)與算法雖然沒有本蛋這么大的夢想，但是它的出現(xiàn)也是想著花更少的時間和更少的存儲來解決問題。
那如何去考量“更少的時間和更少的存儲”，復(fù)雜度分析為此而生。
既然你誠心誠意的不知道，那我就大發(fā)慈悲的打個不恰當(dāng)?shù)谋确健?/span>
如果把數(shù)據(jù)結(jié)構(gòu)與算法看成武功招式，那復(fù)雜度分析就是對應(yīng)的心法。
如果只是學(xué)會了數(shù)據(jù)結(jié)構(gòu)與算法的用法，不學(xué)復(fù)雜度分析，這就和你費盡千辛萬苦在隔壁老王家次臥進(jìn)門右手第二塊地磚下偷挖出老王打遍村里無敵手的村林至寶王霸拳，然后發(fā)現(xiàn)秘籍上只有招式，沒有內(nèi)功心法，好好得王霸拳變的還不如王八拳。只有學(xué)會了王霸之氣，才能虎軀一震，王霸之氣一噗，震走村口光棍李養(yǎng)的哈巴狗。
吐樣吐森破！吃葡萄不吐葡萄皮！
你們說的這種主流叫做事后統(tǒng)計法。
簡單來說，就是你需要提前寫好算法代碼和編好測試數(shù)據(jù)，然后在計算機上跑，通過最后得出的運行時間判斷算法時效的高低，這里的運行時間就是我們?nèi)粘５臅r間。
我且不用“萬一你費勁心思寫好的算法代碼本身是個很糟糕的解法”這種理由去反駁你，事后統(tǒng)計法本身存在很多缺陷，它并不是一個對我們來說有用的度量指標(biāo)：
首先，事后統(tǒng)計法太依賴計算機的軟件和硬件等性能。代碼在 core i7 處理器的就比 core i5 處理器的運算速度快，更不用說不同的操作系統(tǒng)、不同的編程語言等軟件方面，就算是在同一臺電腦上，用的所有的東西都一樣，內(nèi)存的占用或者是 CPU 的使用率也會造成運行時間的差異。
再者，事后統(tǒng)計法太依賴于測試數(shù)據(jù)集的規(guī)模。同樣是排序算法，你隨便整 5 個 10 個的數(shù)排序，就算最垃圾的排序算法，也看起來快的和法拉利一樣，如果是來10w 個 100w 個，那不同的算法的差距就很大了，而且同樣是 10w 個 100w 個數(shù)，順序和亂序的時間又不同了。
那么問題來了，到底測試數(shù)據(jù)集選多少個合適？數(shù)據(jù)的順序如何定又算合適？
說不出來了叭？
可以看出，我們需要一個不依賴于性能和規(guī)模等外力影響就可以估算算法效率、判斷算法優(yōu)劣的度量指標(biāo)，而復(fù)雜度分析天生就是干這個的，這也是為什么我們要學(xué)習(xí)并必須學(xué)會復(fù)雜度分析！
時間復(fù)雜度
時間復(fù)雜度，也就是指算法的運行時間。
對于某一問題的不同解決算法，運行時間越短算法效率越高，相反，運行時間越長，算法效率越低。
那么如何估算時間復(fù)雜度呢？
大佬們在拽掉腦闊上最后一根頭發(fā)的時候發(fā)現(xiàn)，當(dāng)用運行時間去描述一個算法快慢的時候，算法中執(zhí)行的總步數(shù)顯得尤為重要。
因為只是估算，我們可以假設(shè)每一行代碼的運行時間都為一個 Btime，那么算法的總的運行時間 = 運行的總代碼行數(shù)。
下面我們來看這么一段簡單的代碼。
def dogeggs_sum (n):sum = 0for dogegg in range(n):sum += dogeggreturn sum
在上面假設(shè)的情況下，這段求累加和的代碼總的運行時間是多少呢？
第 2 行代碼需要 1 Btime 的運行時間，第 4 和 第 5行分別運行了 n 次，所以每個需要 n * Btime 的運行時間，所以總的運行時間就是 (1 + 2n) * Btime。
我們一般用 T 函數(shù)來表示賦值語句的總運行時間，所以上面總的運行時間就可以表達(dá)成 T(n) = (1 + 2n) * Btime，翻譯一下就是“數(shù)據(jù)集大小為 n，總步數(shù)為 (1 + 2n) 的算法的執(zhí)行時間為 T(n)”。
通過公式，我們可以看出 T(n) 和總步數(shù)是成正比關(guān)系，這個規(guī)律的發(fā)現(xiàn)其實是很重要的，因為這個告訴了我們一種趨勢，數(shù)據(jù)集規(guī)模和運行時間之間有趨勢！
所有人準(zhǔn)備，我們很熟悉的大 O 閃亮登場了！
大 O 表示法
大 O 表示法，表示的是算法有多快。
這個多快，不是說算法代碼真正的運行時間，而是代表著一種趨勢，一種隨著數(shù)據(jù)集的規(guī)模增大，算法代碼運行時間變化的一種趨勢。一般記作 Ｏ(f(n))。
那么之前的公式就變成 T(n) = O(f(n))，其中 f(n) 是算法代碼執(zhí)行的總步數(shù)，也叫操作數(shù)。
n 作為數(shù)據(jù)集大小，它可以取 1，10，100，1000 或者更大更大更大的數(shù)，到這你就會發(fā)現(xiàn)一件很有意思的事兒，那就是當(dāng)數(shù)據(jù)集越來越大時，你會發(fā)現(xiàn)代碼中的某些部分“失效”了。
還是以之前的代碼為例。當(dāng) n = 1000 時，1 + 2n = 2001，當(dāng) n = 10000 時，1 + 2n = 20001，當(dāng)這個 n 持續(xù)增大時，常數(shù) 1 和系數(shù) 2 對于最后的結(jié)果越來越?jīng)]存在感，即對趨勢的變化影響不大。
所以對于我們這段代碼樣例，最終的 T(n) = O(n)。
接下來再用兩段代碼進(jìn)一步學(xué)一下求時間復(fù)雜度分析。
時間復(fù)雜度分析
代碼 1
def dogeggs_sum (n):sum = 0for dogegg in range(n):for i in range(n):sum += dogegg * ireturn sum
這段代碼我會從最開始一點點帶你來。
第 2 行需要運行 1 次 ，第 4 行需要運行 n 次，第 5 行和第 6 行分別需要運行 n2 次。所以總的運行次數(shù) f(n) = 1 + n + 2n2。
當(dāng) n 為 5 的時候，f(n) = 1 + 5 + 2 * 25，當(dāng) n 為 10000 的時候，f(n) = 1 + 10000 + 2 * 100000000，當(dāng) n 更大呢？
這個時候其實很明顯的就可以看出來 n2 起到了決定性的作用，像常數(shù) 1，一階 n 和 系數(shù) 2 對最終的結(jié)果（即趨勢）影響不大，所以我們可以把它們直接忽略掉，所以執(zhí)行的總步數(shù)就可以看成是“主導(dǎo)”結(jié)果的那個，也就是 f(n) = n2。
自然代碼的運行時間 T(n) = O(f(n)) = O(n2)。
代碼 2
def dogeggs_sum (n):sum1 = 0for dogegg1 in range(n):sum1 += dogegg1sum2 = 0for dogegg2 in range(n):for i in range(n):sum2 += dogegg2 * isum3 = 0for dogegg3 in range(n):for i in range(n):for j in range(n):sum3 += dogegg3 * i * jreturn sum1 + sum2 + sum3
上面這段代碼是求三部分的和，經(jīng)過之前的學(xué)習(xí)應(yīng)該很容易知道，第一部分的時間復(fù)雜度是 O(n)，第二部分的時間復(fù)雜度是 O(n2)，第三部分是 O(n3)。
正常來講，這段代碼的 T(n) = O(n) + O(n2) + O(n3)，按照我們?nèi) 爸鲗?dǎo)”部分，顯然前面兩個小弟都應(yīng)該直接 pass，最終 T(n) = O(n3)。
通過這幾個例子，聰明的小婊貝們肯定會發(fā)現(xiàn)，對于時間復(fù)雜度分析來說，只要找起“主導(dǎo)”作用的部分代碼即可，這個主導(dǎo)就是最高的那個復(fù)雜度，也就是執(zhí)行次數(shù)最多的那部分 n 的量級。
剩下的就是多加練習(xí)，有意識的多去想多去練，就可以和我一樣 帥氣 穩(wěn)啦。
常見時間復(fù)雜度
算法學(xué)習(xí)過程中，我們會遇到各種各樣的時間復(fù)雜度，但縱使你代碼七十二變，幾乎也逃不過下面這幾種常見的時間復(fù)雜度。
| 時間復(fù)雜度 | 階 | f(n) 舉例 |
| 常數(shù)復(fù)雜度 | O(1) | 1 |
| 對數(shù)復(fù)雜度 | O(logn) | logn + 1 |
| 線性復(fù)雜度 | O(n) | n + 1 |
| 線性對數(shù)復(fù)雜度 | O(nlogn) | nlogn + 1 |
| k 次復(fù)雜度 | O(n2)、O(n3)、.... | n2 + n +1 |
| 指數(shù)復(fù)雜度 | O(2n) | 2n + 1 |
| 階乘復(fù)雜度 | O(n!) | n! + 1 |
上表的時間復(fù)雜度由上往下依次增加，O(n) 和 O(n2) 前面已經(jīng)講過了，O(2n) 和 O(n!) 效率低到離譜，以后不幸碰到我再提一下，就不再贅述。
下面主要來看剩下幾種最常見的時間復(fù)雜度。
O(1)
O(1) 是常數(shù)時間復(fù)雜度。
在這你要先明白一個概念，不是只執(zhí)行 1 次的代碼的時間復(fù)雜度記為 O(1)，只要你是常數(shù)，像 O(2)、O(3) ... O(100000) 在復(fù)雜度的表示上都是 O(1)。
n = 10000res = n / 2print(res)
比如像上面這段代碼，它運行了 3 次，但是它的時間復(fù)雜度記為 O(1)，而不是 O(3)。
因為無論 n 等于多少，對于它們每行代碼來說還是只是執(zhí)行了一次，代碼的執(zhí)行時間不隨 n 的變化而變化。
O(logn)
O(logn) 是對數(shù)時間復(fù)雜度。首先我們來看一段代碼：
dogegg = 1while dogegg < n:dogegg = dogegg * 2
根據(jù)之前講的，我們先找“主導(dǎo)”，在這主導(dǎo)就是第 4 行代碼，只要算出它的時間復(fù)雜度，總的時間復(fù)雜度就知道了。
其實很簡單，上面的代碼翻譯一下就是初始化 dogegg = 1， 乘上多少個 2 以后會 ≥ n。
假設(shè)需要 x 個，那么相當(dāng)于求：
即：
所以上述代碼的時間復(fù)雜度應(yīng)該為 O(log2n)。
但是對于對數(shù)復(fù)雜度來說，不管你是以 2、3 為底，還是以 10 為底，通通記作 O(logn)，這是為什么呢？
這就要從對數(shù)的換底公式說起。
根據(jù)換底公式，log2n 可以寫成：
對于時間復(fù)雜度來說：
所以在對數(shù)時間復(fù)雜度中我們就忽略了底，直接用 O(logn) 來表示對數(shù)時間復(fù)雜度。
O(nlogn)
O(nlogn)，真的是很常見的時間復(fù)雜度，像后面會學(xué)到的快速排序、歸并排序的時間復(fù)雜度都是 O(nlogn)。
如果只是簡單看的話是在 logn 外面套了層 for 循環(huán)，比如像下面這段代碼：
def stupid_cnt(n):cnt = 0for i in range(n):dogegg = 1while dogegg < n:dogegg = dogegg * 2cnt += 1return cnt
當(dāng)然像上面這種 stupid 代碼一般人不會寫，我也只是舉個例子給大家看，我是狗蛋，大家千萬不要以為我是傻狗。
最好情況、最壞情況和平均情況時間復(fù)雜度
除了數(shù)據(jù)集規(guī)模影響算法的運行時間外，“數(shù)據(jù)的具體情況”也會影響到運行時間。
我們來看這么一段代碼：
def find_word(lst, word):flag = -1for i in range(len(lst)):if lst[i] == word:flag = ibreakreturn flag
上面這段簡單代碼是求變量 word 在列表 lst 中出現(xiàn)的位置，我用這段來解釋“數(shù)據(jù)的具體情況”是什么意思。
變量 word 可能出現(xiàn)在列表 lst 的任意位置，假設(shè) a = ['a', 'b', 'c', 'd']：
當(dāng) word = 'a' 時，正好是列表 lst 的第 1 個，后面的不需要再遍歷，那么本情況下的時間復(fù)雜度是 O(1)。
當(dāng) word = 'd' 或者 word = 'e' 時，這兩種情況是整個列表全部遍歷完，那么這些情況下的時間復(fù)雜度是 O(n)。
這就是數(shù)據(jù)的具體情況不同，代碼的時間復(fù)雜度不同。
根據(jù)不同情況，我們有了最好情況時間復(fù)雜度、最壞情況時間復(fù)雜度和平均情況時間復(fù)雜度這 3 個概念。
最好情況時間復(fù)雜度
最好情況就是在最理想的情況下，代碼的時間復(fù)雜度。對應(yīng)上例變量 word 正好是列表 lst 的第 1 個，這個時候?qū)?yīng)的時間復(fù)雜度 O(1) 就是這段代碼的最好情況時間復(fù)雜度。
最壞情況時間復(fù)雜度
最壞情況就是在最差的情況下，代碼的時間復(fù)雜度。對應(yīng)上例變量 word 正好是列表 lst 的最后一個，或者 word 不存在于列表 lst，這個時候?qū)?yīng)的時間復(fù)雜度 O(n) 是這段代碼的最壞情況時間復(fù)雜度。
平均情況時間復(fù)雜度
大多數(shù)情況下，代碼的執(zhí)行情況都是介于最好情況和最壞情況之間，所以又出現(xiàn)了平均情況時間復(fù)雜度。
那怎么計算平均時間復(fù)雜度呢？這個說起來有點復(fù)雜，需要用到概率論的知識。
在這里我還是用上面的例子來講，因為只是簡單的科普一下，為了方便計算，我假設(shè)的會有點隨意：
從大的方面來看，查找變量 x 在列表 lst 中的位置有兩種情況：在或者不在。假設(shè)變量 x 在或者不在列表 lst 中的概率都為 1/2。
如果 x 在列表 lst 中，那么 x 有 n 種情況，它可能出現(xiàn)在 0 到 n-1 中任意位置，假設(shè)出現(xiàn)在每個位置的概率都相同，都為 1/n。
每個出現(xiàn)的概率（即權(quán)重）知道了，所以平均時間復(fù)雜度為：
是不是看著有點眼熟，這就是我們都學(xué)過的加權(quán)平均值。
什么，沒學(xué)過？問題不大。加權(quán)平均值就是將各數(shù)值乘以相應(yīng)的權(quán)數(shù)，然后加總求和得到總體值，再除以總的單位數(shù)。
所以最終的平均時間復(fù)雜度就為：
最好情況，反應(yīng)最理想的情況，怎么可能天上天天掉餡餅，沒啥參考價值。
平均情況，這倒是能反映算法的全面情況，但是一般“全面”，就和什么都沒說一樣，也沒啥參考價值。
最壞情況，干啥事情都要考慮最壞的結(jié)果，因為最壞的結(jié)果提供了一種保障，觸底的保障，保障代碼的運行時間這個就是最差的，不會有比它還差的。
所以，不需要糾結(jié)各種情況，算時間復(fù)雜度就算最壞的那個時間復(fù)雜度即可。
空間復(fù)雜度
空間復(fù)雜度相較于時間復(fù)雜度來說，比較簡單，需要掌握的內(nèi)容不多。
空間復(fù)雜度和時間復(fù)雜度一樣，反映的也是一種趨勢，只不過這種趨勢是代碼運行過程中臨時變量占用的內(nèi)存空間。
代碼在計算機中的運行所占用的存儲空間吶，主要分為 3 部分：
代碼本身所占用的
輸入數(shù)據(jù)所占用的
臨時變量所占用的
前面兩個部分是本身就要占這些空間，與代碼的性能無關(guān)，所以我們在衡量代碼的空間復(fù)雜度的時候，只關(guān)心運行過程中臨時占用的內(nèi)存空間。
空間復(fù)雜度記作 S(n)，表示形式與時間復(fù)雜度一致。
在這同樣 n 作為數(shù)據(jù)集大小，f(n) 指的是規(guī)模 n 所占存儲空間的函數(shù)。
空間復(fù)雜度分析
下面我們用一段簡單代碼來學(xué)習(xí)下如何分析空間復(fù)雜度。
def dogeggs_sum(lst):sum = 0for i in range(len(lst)):sum += lst[i]return sum
上述代碼是求列表 lst 的所有元素之和，根據(jù)之前說的，只計算臨時變量所占用的內(nèi)存空間。
形參 lst 所占的空間不計，那么剩下的臨時變量只有 sum 和 i，sum 是存儲和，是常數(shù)階，i 是存儲元素位置，也是常數(shù)階，它倆所分配的空間和規(guī)模 n 都沒有關(guān)系，所以整段代碼的空間復(fù)雜度 S(n) = O(1)。
常見空間復(fù)雜度
常見的空間復(fù)雜度有 O(1)、O(n)、O(n2)，O(1) 在上節(jié)講了，還有就是像 O(logn) 這種也有，但是等閑不會碰到，在這里就不羅嗦了。
O(n)
def create_lst(n):lst = []for i in range(n):lst.append(i)return lst
上面這段傻傻的代碼有兩個臨時變量 lst 和 i。
其中 lst 是被創(chuàng)建的一個空列表，這個列表占用的內(nèi)存隨著 for 循環(huán)的增加而增加，最大到 n，所以 lst 的空間復(fù)雜度為 O(n)，i 是存儲元素位置的常數(shù)階，與規(guī)模 n 無關(guān)，所以這段代碼最終的空間復(fù)雜度為 O(n)。
O(n2)
def create_lst(n):lst1 = []for i in range(n):lst2 = []for j in range(n):lst2.append(j)lst1.append(lst2)return lst1
還是一樣的分析方式，很明顯上面這段傻二次方的代碼創(chuàng)建了一個二維數(shù)組 lst，一維 lst1 占用 n，二維 lst2 占用 n2，所以最終這段代碼的空間復(fù)雜度為 O(n2)。
到這里，復(fù)雜度分析就全部講完啦，只要臭寶們認(rèn)真看完這篇文章，相信會對復(fù)雜度分析有個基本的認(rèn)識。復(fù)雜度分析本身不難，只要多加練習(xí)，平時寫代碼的時候有意識的多想估算一下自己的代碼，感覺就會慢慢來啦。
這是公眾號的第一篇，寫完真心不太容易，希望開了個好頭。碼字不易，臭寶們多多支持呀，點贊在看留言么么噠呀。
我是蛋蛋，我們下次見～
