保姆級教學！徹底學會時間復雜度和空間復雜度

大家好，我是蛋蛋，

資料結構與演算法，作為編程界從入門到勸退的王者，是很多初學者心中神圣而想侵犯的村花兒，化身舔狗，費盡心思，舔到最后，我命油我不油天，

作為一名大學之前編程能力為零，以為計算機專業就是打游戲的咸魚，到參加 ACM 競賽，靠著劃水和抱大腿拿了幾塊金銀銅鐵牌的前 ACM 混子選手，想起之前瘋狂跪舔資料結構和演算法的日子，至今我扔能掬出一把辛酸淚，

為了讓臭寶們不再像我這樣當個人這么難，我決定和大家一起學習資料結構與演算法，我希望能用傻瓜的方式，由淺入深，從概念到實踐，一步一步的來，這個程序可能會很長，我希望在這個程序中你能喜歡上它，能發現它們冰冷外表下有趣的靈魂，

學習資料結構與演算法的第一課，我永遠都選復雜度分析，在我看來，這是資料結構與演算法中最重要的知識點，且不接受任何反駁，

復雜度分析主要就是時間復雜度和空間復雜度，接下來的文章也主要圍繞這兩方面來講，廢話不多說，前排馬扎瓜子準備好，蛋蛋小課堂正式接客圖片

復雜度分析

剛剛我說過，在本蛋看來，復雜度分析是資料結構和演算法中最重要的知識點，毫不夸張的說，這就是資料結構與演算法學習的核心所在，你學會了它你就入的了門，你學不會它，你就永遠不知道門兒在哪，

為什么復雜度分析會這么重要？

這個就要從盤古開天辟地，呃，從資料結構與演算法的本身說起，

我平常白天做夢的時候，總是想著當當咸魚劃劃水就能賺大錢，最好就是能躺著，錢就直接砸到我腦闊上，資料結構與演算法雖然沒有本蛋這么大的夢想，但是它的出現也是想著花更少的時間和更少的存盤來解決問題，

那如何去考量“更少的時間和更少的存盤”，復雜度分析為此而生，

蛋蛋：所以為什么復雜度分析重要你們知道了叭？
臭寶：不知道不知道
蛋蛋：啥？還不知道？？？
臭寶：對呀對呀
蛋蛋：，，，

既然你誠心誠意的不知道，那我就大發慈悲的打個不恰當的比方，

如果把資料結構與演算法看成武功招式，那復雜度分析就是對應的心法，

如果只是學會了資料結構與演算法的用法，不學復雜度分析，這就和你費盡千辛萬苦在隔壁老王家次臥進門右手第二塊地磚下偷挖出老王打遍村里無敵手的村林至寶王霸拳，然后發現秘籍上只有招式，沒有內功心法，好好得王霸拳變的還不如王八拳，只有學會了王霸之氣，才能虎軀一震，王霸之氣一噗，震走村口光棍李養的哈巴狗，

臭寶：哇，厲害厲害厲害，你胖你說的都對，但還是沒必要學啊，
蛋蛋：？？？
臭寶：現在有很多工具啊包啊，代碼隨便跑一下，就能輕輕松松知道運行了多少時間占了多少記憶體啊，演算法的效率不就輕松比對出來了么？
蛋蛋：，，，

吐樣吐森破！吃葡萄不吐葡萄皮！

你們說的這種主流叫做事后統計法，

簡單來說，就是你需要提前寫好演算法代碼和編好測驗資料，然后在計算機上跑，通過最后得出的運行時間判斷演算法時效的高低，這里的運行時間就是我們日常的時間，

我且不用“萬一你費勁心思寫好的演算法代碼本身是個很糟糕的解法”這種理由去反駁你，事后統計法本身存在很多缺陷，它并不是一個對我們來說有用的度量指標：

首先，事后統計法太依賴計算機的軟體和硬體等性能，代碼在 core i7 處理器的就比 core i5 處理器的運算速度快，更不用說不同的作業系統、不同的編程語言等軟體方面，就算是在同一臺電腦上，用的所有的東西都一樣，記憶體的占用或者是 CPU 的使用率也會造成運行時間的差異，

再者，事后統計法太依賴于測驗資料集的規模，同樣是排序演算法，你隨便整 5 個 10 個的數排序，就算最垃圾的排序演算法，也看起來快的和法拉利一樣，如果是來10w 個 100w 個，那不同的演算法的差距就很大了，而且同樣是 10w 個 100w 個數，順序和亂序的時間又不同了，

那么問題來了，到底測驗資料集選多少個合適？資料的順序如何定又算合適？

說不出來了叭？

可以看出，我們需要一個不依賴于性能和規模等外力影響就可以估算演算法效率、判斷演算法優劣的度量指標，而復雜度分析天生就是干這個的，這也是為什么我們要學習并必須學會復雜度分析！

時間復雜度

時間復雜度，也就是指演算法的運行時間，

對于某一問題的不同解決演算法，運行時間越短演算法效率越高，相反，運行時間越長，演算法效率越低，

那么如何估算時間復雜度呢？

大佬們在拽掉腦闊上最后一根頭發的時候發現，當用運行時間去描述一個演算法快慢的時候，演算法中執行的總步數顯得尤為重要，

因為只是估算，我們可以假設每一行代碼的運行時間都為一個 Btime，那么演算法的總的運行時間 = 運行的總代碼行數，

下面我們來看這么一段簡單的代碼，

def dogeggs_sum (n):
    sum = 0
    
    for dogegg in range(n):
        sum += dogegg
    return sum

在上面假設的情況下，這段求累加和的代碼總的運行時間是多少呢？

第 2 行代碼需要 1 Btime 的運行時間，第 4 和 第 5行分別運行了 n 次，所以每個需要 n * Btime 的運行時間，所以總的運行時間就是 (1 + 2n) * Btime，

我們一般用T 函式來表示賦值陳述句的總運行時間，所以上面總的運行時間就可以表達成 T(n) = (1 + 2n) * Btime，翻譯一下就是“資料集大小為 n，總步數為 (1 + 2n) 的演算法的執行時間為 T(n)”，

通過公式，我們可以看出 T(n) 和總步數是成正比關系，這個規律的發現其實是很重要的，因為這個告訴了我們一種趨勢，資料集規模和運行時間之間有趨勢！

所有人準備，我們很熟悉的大 O 閃亮登場了！

大 O 表示法

大 O 表示法，表示的是演算法有多快，

這個多快，不是說演算法代碼真正的運行時間，而是代表著一種趨勢，一種隨著資料集的規模增大，演算法代碼運行時間變化的一種趨勢，一般記作 Ｏ(f(n))，

那么之前的公式就變成 T(n) = O(f(n))，其中 f(n) 是演算法代碼執行的總步數，也叫運算元，

n 作為資料集大小，它可以取 1，10，100，1000 或者更大更大更大的數，到這你就會發現一件很有意思的事兒，那就是當資料集越來越大時，你會發現代碼中的某些部分“失效”了，

還是以之前的代碼為例，當 n = 1000 時，1 + 2n = 2001，當 n = 10000 時，1 + 2n = 20001，當這個 n 持續增大時，常數 1 和系數 2 對于最后的結果越來越沒存在感，即對趨勢的變化影響不大，

所以對于我們這段代碼樣例，最終的 T(n) = O(n)，

接下來再用兩段代碼進一步學一下求時間復雜度分析，

時間復雜度分析

代碼 1

def dogeggs_sum (n):
    sum = 0

    for dogegg in range(n):
        for i in range(n):
            sum += dogegg * i
    return sum

這段代碼我會從最開始一點點帶你來，

第 2 行需要運行 1 次 ，第 4 行需要運行 n 次，第 5 行和第 6 行分別需要運行 n2 次，所以總的運行次數 f(n) = 1 + n + 2n2，

當 n 為 5 的時候，f(n) = 1 + 5 + 2 * 25，當 n 為 10000 的時候，f(n) = 1 + 10000 + 2 * 100000000，當 n 更大呢？

這個時候其實很明顯的就可以看出來 n2 起到了決定性的作用，像常數 1，一階 n 和 系數 2 對最終的結果（即趨勢）影響不大，所以我們可以把它們直接忽略掉，所以執行的總步數就可以看成是“主導”結果的那個，也就是 f(n) = n2，

自然代碼的運行時間 T(n) = O(f(n)) = O(n2)，

代碼 2

def dogeggs_sum (n):
    sum1 = 0
    for dogegg1 in range(n):
        sum1 += dogegg1

    sum2 = 0
    for dogegg2 in range(n):
        for i in range(n):
            sum2 += dogegg2 * i

    sum3 = 0
    for dogegg3 in range(n):
        for i in range(n):
            for j in range(n):
                sum3 += dogegg3 * i * j

    return sum1 + sum2 + sum3

上面這段代碼是求三部分的和，經過之前的學習應該很容易知道，第一部分的時間復雜度是 O(n)，第二部分的時間復雜度是 O(n2)，第三部分是 O(n3)，

正常來講，這段代碼的 T(n) = O(n) + O(n2) + O(n3)，按照我們取“主導”部分，顯然前面兩個小弟都應該直接 pass，最終 T(n) = O(n3)，

通過這幾個例子，聰明的小婊貝們肯定會發現，對于時間復雜度分析來說，只要找起“主導”作用的部分代碼即可，這個主導就是最高的那個復雜度，也就是執行次數最多的那部分 n 的量級，

剩下的就是多加練習，有意識的多去想多去練，就可以和我一樣 帥氣 穩啦，

這里推薦兩個比較好的資料，一份是筆記，一份最優解，兩者加起來無敵，
兩個月斬獲 70k star，前位元組大神刷題筆記
清華學霸的刷題筆記(leetcode最優解)

常見時間復雜度

演算法學習程序中，我們會遇到各種各樣的時間復雜度，但縱使你代碼七十二變，幾乎也逃不過下面這幾種常見的時間復雜度，

上表的時間復雜度由上往下依次增加，O(n) 和 O(n2) 前面已經講過了，O(2n) 和 O(n!) 效率低到離譜，以后不幸碰到我再提一下，就不再贅述，

下面主要來看剩下幾種最常見的時間復雜度，

O(1)

O(1) 是常數時間復雜度，

在這你要先明白一個概念，不是只執行 1 次的代碼的時間復雜度記為 O(1)，只要你是常數，像 O(2)、O(3) … O(100000) 在復雜度的表示上都是 O(1)，

n = 10000
res = n / 2 
print(res)

比如像上面這段代碼，它運行了 3 次，但是它的時間復雜度記為 O(1)，而不是 O(3)，

因為無論 n 等于多少，對于它們每行代碼來說還是只是執行了一次，代碼的執行時間不隨 n 的變化而變化，

O(logn)

O(logn) 是對數時間復雜度，首先我們來看一段代碼：

dogegg = 1

while dogegg < n:
    dogegg = dogegg * 2

根據之前講的，我們先找“主導”，在這主導就是第 4 行代碼，只要算出它的時間復雜度，總的時間復雜度就知道了，

其實很簡單，上面的代碼翻譯一下就是初始化 dogegg = 1， 乘上多少個 2 以后會 ≥ n，

假設需要 x 個，那么相當于求：

即：

所以上述代碼的時間復雜度應該為 O(log2n)，

但是對于對數復雜度來說，不管你是以 2、3 為底，還是以 10 為底，通通記作 O(logn)，這是為什么呢？

這就要從對數的換底公式說起，

根據換底公式，log2n 可以寫成：

對于時間復雜度來說：

所以在對數時間復雜度中我們就忽略了底，直接用 O(logn) 來表示對數時間復雜度，

O(nlogn)

O(nlogn)，真的是很常見的時間復雜度，像后面會學到的快速排序、歸并排序的時間復雜度都是 O(nlogn)，

如果只是簡單看的話是在 logn 外面套了層 for 回圈，比如像下面這段代碼：

def stupid_cnt(n):
    cnt = 0
    for i in range(n):
        dogegg = 1

        while dogegg < n:
            dogegg = dogegg * 2
            cnt += 1
    return cnt

當然像上面這種 stupid 代碼一般人不會寫，我也只是舉個例子給大家看，我是狗蛋，大家千萬不要以為我是傻狗，

最好情況、最壞情況和平均情況時間復雜度

除了資料集規模影響演算法的運行時間外，“資料的具體情況”也會影響到運行時間，

我們來看這么一段代碼：

def find_word(lst, word):

    flag = -1
    for i in range(len(lst)):
        if lst[i] == word:
            flag = i
            break

    return flag

上面這段簡單代碼是求變數 word 在串列 lst 中出現的位置，我用這段來解釋“資料的具體情況”是什么意思，

變數 word 可能出現在串列 lst 的任意位置，假設 a = [‘a’, ‘b’, ‘c’, ‘d’]：

• 當 word = ‘a’ 時，正好是串列 lst 的第 1 個，后面的不需要再遍歷，那么本情況下的時間復雜度是 O(1)，

• 當 word = ‘d’ 或者 word = ‘e’ 時，這兩種情況是整個串列全部遍歷完，那么這些情況下的時間復雜度是 O(n)，

這就是資料的具體情況不同，代碼的時間復雜度不同，

根據不同情況，我們有了最好情況時間復雜度、最壞情況時間復雜度和平均情況時間復雜度這 3 個概念，

最好情況時間復雜度

最好情況就是在最理想的情況下，代碼的時間復雜度，對應上例變數 word 正好是串列 lst 的第 1 個，這個時候對應的時間復雜度 O(1) 就是這段代碼的最好情況時間復雜度，

最壞情況時間復雜度

最壞情況就是在最差的情況下，代碼的時間復雜度，對應上例變數 word 正好是串列 lst 的最后一個，或者 word 不存在于串列 lst，這個時候對應的時間復雜度 O(n) 是這段代碼的最壞情況時間復雜度，

平均情況時間復雜度

大多數情況下，代碼的執行情況都是介于最好情況和最壞情況之間，所以又出現了平均情況時間復雜度，

那怎么計算平均時間復雜度呢？這個說起來有點復雜，需要用到概率論的知識，

在這里我還是用上面的例子來講，因為只是簡單的科普一下，為了方便計算，我假設的會有點隨意：

• 從大的方面來看，查找變數 x 在串列 lst 中的位置有兩種情況：在或者不在，假設變數 x 在或者不在串列 lst 中的概率都為 1/2，

• 如果 x 在串列 lst 中，那么 x 有 n 種情況，它可能出現在 0 到 n-1 中任意位置，假設出現在每個位置的概率都相同，都為 1/n，

每個出現的概率（即權重）知道了，所以平均時間復雜度為：

是不是看著有點眼熟，這就是我們都學過的加權平均值，

什么，沒學過？問題不大，加權平均值就是將各數值乘以相應的權數，然后加總求和得到總體值，再除以總的單位數，

所以最終的平均時間復雜度就為：

臭寶：又是最好，又是最壞，又是平均的，這么多到呼叫哪個呀？
蛋蛋：這個還用問？當然是選擇最壞情況時間復雜度啊！

最好情況，反應最理想的情況，怎么可能天上天天掉餡餅，沒啥參考價值，

平均情況，這倒是能反映演算法的全面情況，但是一般“全面”，就和什么都沒說一樣，也沒啥參考價值，

最壞情況，干啥事情都要考慮最壞的結果，因為最壞的結果提供了一種保障，觸底的保障，保障代碼的運行時間這個就是最差的，不會有比它還差的，

所以，不需要糾結各種情況，算時間復雜度就算最壞的那個時間復雜度即可，

空間復雜度

空間復雜度相較于時間復雜度來說，比較簡單，需要掌握的內容不多，

空間復雜度和時間復雜度一樣，反映的也是一種趨勢，只不過這種趨勢是代碼運行程序中臨時變數占用的記憶體空間，

臭寶：為什么是“臨時”咧？
蛋蛋：這就要從代碼在計算機中的運行說起啦，

代碼在計算機中的運行所占用的存盤空間吶，主要分為 3 部分：

• 代碼本身所占用的
• 輸入資料所占用的
• 臨時變數所占用的

前面兩個部分是本身就要占這些空間，與代碼的性能無關，所以我們在衡量代碼的空間復雜度的時候，只關心運行程序中臨時占用的記憶體空間，

空間復雜度記作 S(n)，表示形式與時間復雜度一致，

在這同樣 n 作為資料集大小，f(n) 指的是規模 n 所占存盤空間的函式，

空間復雜度分析

下面我們用一段簡單代碼來學習下如何分析空間復雜度，

def dogeggs_sum(lst):
    sum = 0
    for i in range(len(lst)):
        sum += lst[i]

    return sum

上述代碼是求串列 lst 的所有元素之和，根據之前說的，只計算臨時變數所占用的記憶體空間，

形參 lst 所占的空間不計，那么剩下的臨時變數只有 sum 和 i，sum 是存盤和，是常數階，i 是存盤元素位置，也是常數階，它倆所分配的空間和規模 n 都沒有關系，所以整段代碼的空間復雜度 S(n) = O(1)，

常見空間復雜度

常見的空間復雜度有 O(1)、O(n)、O(n2)，O(1) 在上節講了，還有就是像 O(logn) 這種也有，但是等閑不會碰到，在這里就不羅嗦了，

O(n)

def create_lst(n):
    lst = []
    for i in range(n):
        lst.append(i)

    return lst

上面這段傻傻的代碼有兩個臨時變數 lst 和 i，

其中 lst 是被創建的一個空串列，這個串列占用的記憶體隨著 for 回圈的增加而增加，最大到 n，所以 lst 的空間復雜度為 O(n)，i 是存盤元素位置的常數階，與規模 n 無關，所以這段代碼最終的空間復雜度為 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

還是一樣的分析方式，很明顯上面這段傻二次方的代碼創建了一個二維陣列 lst，一維 lst1 占用 n，二維 lst2 占用 n2，所以最終這段代碼的空間復雜度為 O(n2)，

到這里，復雜度分析就全部講完啦，只要臭寶們認真看完這篇文章，相信會對復雜度分析有個基本的認識，復雜度分析本身不難，只要多加練習，平時寫代碼的時候有意識的多想估算一下自己的代碼，感覺就會慢慢來啦，

這是玩轉資料結構與演算法的第一篇，寫完真心不太容易，希望開了個好頭，碼字不易，臭寶們多多支持呀，一鍵三連再來留言，么么噠呀，

我們下次見～