大家好，我是蛋蛋。

數(shù)據(jù)結(jié)構(gòu)與算法，作為編程界從入門到勸退的王者，是很多初學(xué)者心中神圣而想侵犯的村花兒，化身舔狗，費(fèi)盡心思，舔到最后，我命油我不油天。

作為一名大學(xué)之前編程能力為零，以為計(jì)算機(jī)專業(yè)就是打游戲的咸魚，到參加 ACM 競(jìng)賽，靠著劃水和抱大腿拿了幾塊金銀銅鐵牌的前 ACM 混子選手，想起之前瘋狂跪舔數(shù)據(jù)結(jié)構(gòu)和算法的日子，至今我扔能掬出一把辛酸淚。

為了讓臭寶們不再像我這樣當(dāng)個(gè)人這么難，我決定和大家一起學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法，我希望能用傻瓜的方式，由淺入深，從概念到實(shí)踐，一步一步的來(lái)，這個(gè)過(guò)程可能會(huì)很長(zhǎng)，我希望在這個(gè)過(guò)程中你能喜歡上它，能發(fā)現(xiàn)它們冰冷外表下有趣的靈魂。

學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的第一課，我永遠(yuǎn)都選復(fù)雜度分析，在我看來(lái)，這是數(shù)據(jù)結(jié)構(gòu)與算法中最重要的知識(shí)點(diǎn)，且不接受任何反駁。

復(fù)雜度分析主要就是時(shí)間復(fù)雜度和空間復(fù)雜度，接下來(lái)的文章也主要圍繞這兩方面來(lái)講。廢話不多說(shuō)，前排馬扎瓜子準(zhǔn)備好，蛋蛋小課堂正式接客圖片

復(fù)雜度分析

剛剛我說(shuō)過(guò)，在本蛋看來(lái)，復(fù)雜度分析是數(shù)據(jù)結(jié)構(gòu)和算法中最重要的知識(shí)點(diǎn)，毫不夸張的說(shuō)，這就是數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)的核心所在。你學(xué)會(huì)了它你就入的了門，你學(xué)不會(huì)它，你就永遠(yuǎn)不知道門兒在哪。

為什么復(fù)雜度分析會(huì)這么重要？

這個(gè)就要從盤古開天辟地，呃，從數(shù)據(jù)結(jié)構(gòu)與算法的本身說(shuō)起。

我平常白天做夢(mèng)的時(shí)候，總是想著當(dāng)當(dāng)咸魚劃劃水就能賺大錢，最好就是能躺著，錢就直接砸到我腦闊上。數(shù)據(jù)結(jié)構(gòu)與算法雖然沒(méi)有本蛋這么大的夢(mèng)想，但是它的出現(xiàn)也是想著花更少的時(shí)間和更少的存儲(chǔ)來(lái)解決問(wèn)題。

那如何去考量“更少的時(shí)間和更少的存儲(chǔ)”，復(fù)雜度分析為此而生。

蛋蛋：所以為什么復(fù)雜度分析重要你們知道了叭？
臭寶：不知道不知道
蛋蛋：啥？還不知道？？？
臭寶：對(duì)呀對(duì)呀
蛋蛋：。。。

既然你誠(chéng)心誠(chéng)意的不知道，那我就大發(fā)慈悲的打個(gè)不恰當(dāng)?shù)谋确健?/p>

如果把數(shù)據(jù)結(jié)構(gòu)與算法看成武功招式，那復(fù)雜度分析就是對(duì)應(yīng)的心法。

如果只是學(xué)會(huì)了數(shù)據(jù)結(jié)構(gòu)與算法的用法，不學(xué)復(fù)雜度分析，這就和你費(fèi)盡千辛萬(wàn)苦在隔壁老王家次臥進(jìn)門右手第二塊地磚下偷挖出老王打遍村里無(wú)敵手的村林至寶王霸拳，然后發(fā)現(xiàn)秘籍上只有招式，沒(méi)有內(nèi)功心法，好好得王霸拳變的還不如王八拳。只有學(xué)會(huì)了王霸之氣，才能虎軀一震，王霸之氣一噗，震走村口光棍李養(yǎng)的哈巴狗。

臭寶：哇，厲害厲害厲害，你胖你說(shuō)的都對(duì)，但還是沒(méi)必要學(xué)啊。
蛋蛋：？？？
臭寶：現(xiàn)在有很多工具啊包啊，代碼隨便跑一下，就能輕輕松松知道運(yùn)行了多少時(shí)間占了多少內(nèi)存啊。算法的效率不就輕松比對(duì)出來(lái)了么？
蛋蛋：。。。

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

你們說(shuō)的這種主流叫做事后統(tǒng)計(jì)法。

簡(jiǎn)單來(lái)說(shuō)，就是你需要提前寫好算法代碼和編好測(cè)試數(shù)據(jù)，然后在計(jì)算機(jī)上跑，通過(guò)最后得出的運(yùn)行時(shí)間判斷算法時(shí)效的高低，這里的運(yùn)行時(shí)間就是我們?nèi)粘５臅r(shí)間。

我且不用“萬(wàn)一你費(fèi)勁心思寫好的算法代碼本身是個(gè)很糟糕的解法”這種理由去反駁你，事后統(tǒng)計(jì)法本身存在很多缺陷，它并不是一個(gè)對(duì)我們來(lái)說(shuō)有用的度量指標(biāo)：

首先，事后統(tǒng)計(jì)法太依賴計(jì)算機(jī)的軟件和硬件等性能。代碼在 core i7 處理器的就比 core i5 處理器的運(yùn)算速度快，更不用說(shuō)不同的操作系統(tǒng)、不同的編程語(yǔ)言等軟件方面，就算是在同一臺(tái)電腦上，用的所有的東西都一樣，內(nèi)存的占用或者是 CPU 的使用率也會(huì)造成運(yùn)行時(shí)間的差異。

再者，事后統(tǒng)計(jì)法太依賴于測(cè)試數(shù)據(jù)集的規(guī)模。同樣是排序算法，你隨便整 5 個(gè) 10 個(gè)的數(shù)排序，就算最垃圾的排序算法，也看起來(lái)快的和法拉利一樣，如果是來(lái)10w 個(gè) 100w 個(gè)，那不同的算法的差距就很大了，而且同樣是 10w 個(gè) 100w 個(gè)數(shù)，順序和亂序的時(shí)間又不同了。

那么問(wèn)題來(lái)了，到底測(cè)試數(shù)據(jù)集選多少個(gè)合適？數(shù)據(jù)的順序如何定又算合適？

說(shuō)不出來(lái)了叭？

可以看出，我們需要一個(gè)不依賴于性能和規(guī)模等外力影響就可以估算算法效率、判斷算法優(yōu)劣的度量指標(biāo)，而復(fù)雜度分析天生就是干這個(gè)的，這也是為什么我們要學(xué)習(xí)并必須學(xué)會(huì)復(fù)雜度分析！

時(shí)間復(fù)雜度

時(shí)間復(fù)雜度，也就是指算法的運(yùn)行時(shí)間。

對(duì)于某一問(wèn)題的不同解決算法，運(yùn)行時(shí)間越短算法效率越高，相反，運(yùn)行時(shí)間越長(zhǎng)，算法效率越低。

那么如何估算時(shí)間復(fù)雜度呢？

大佬們?cè)谧У裟X闊上最后一根頭發(fā)的時(shí)候發(fā)現(xiàn)，當(dāng)用運(yùn)行時(shí)間去描述一個(gè)算法快慢的時(shí)候，算法中執(zhí)行的總步數(shù)顯得尤為重要。

因?yàn)橹皇枪浪悖覀兛梢约僭O(shè)每一行代碼的運(yùn)行時(shí)間都為一個(gè) Btime，那么算法的總的運(yùn)行時(shí)間 = 運(yùn)行的總代碼行數(shù)。

下面我們來(lái)看這么一段簡(jiǎn)單的代碼。

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

在上面假設(shè)的情況下，這段求累加和的代碼總的運(yùn)行時(shí)間是多少呢？

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

我們一般用T 函數(shù)來(lái)表示賦值語(yǔ)句的總運(yùn)行時(shí)間，所以上面總的運(yùn)行時(shí)間就可以表達(dá)成 T(n) = (1 + 2n) * Btime，翻譯一下就是“數(shù)據(jù)集大小為 n，總步數(shù)為 (1 + 2n) 的算法的執(zhí)行時(shí)間為 T(n)”。

通過(guò)公式，我們可以看出 T(n) 和總步數(shù)是成正比關(guān)系，這個(gè)規(guī)律的發(fā)現(xiàn)其實(shí)是很重要的，因?yàn)檫@個(gè)告訴了我們一種趨勢(shì)，數(shù)據(jù)集規(guī)模和運(yùn)行時(shí)間之間有趨勢(shì)！

所有人準(zhǔn)備，我們很熟悉的大 O 閃亮登場(chǎng)了！

大 O 表示法

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

這個(gè)多快，不是說(shuō)算法代碼真正的運(yùn)行時(shí)間，而是代表著一種趨勢(shì)，一種隨著數(shù)據(jù)集的規(guī)模增大，算法代碼運(yùn)行時(shí)間變化的一種趨勢(shì)。一般記作 Ｏ(f(n))。

那么之前的公式就變成 T(n) = O(f(n))，其中 f(n) 是算法代碼執(zhí)行的總步數(shù)，也叫操作數(shù)。

n 作為數(shù)據(jù)集大小，它可以取 1，10，100，1000 或者更大更大更大的數(shù)，到這你就會(huì)發(fā)現(xiàn)一件很有意思的事兒，那就是當(dāng)數(shù)據(jù)集越來(lái)越大時(shí)，你會(huì)發(fā)現(xiàn)代碼中的某些部分“失效”了。

還是以之前的代碼為例。當(dāng) n = 1000 時(shí)，1 + 2n = 2001，當(dāng) n = 10000 時(shí)，1 + 2n = 20001，當(dāng)這個(gè) n 持續(xù)增大時(shí)，常數(shù) 1 和系數(shù) 2 對(duì)于最后的結(jié)果越來(lái)越?jīng)]存在感，即對(duì)趨勢(shì)的變化影響不大。

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

接下來(lái)再用兩段代碼進(jìn)一步學(xué)一下求時(shí)間復(fù)雜度分析。

時(shí)間復(fù)雜度分析

代碼 1

def dogeggs_sum (n):
    sum = 0

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

這段代碼我會(huì)從最開始一點(diǎn)點(diǎn)帶你來(lái)。

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

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

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

自然代碼的運(yùn)行時(shí)間 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

上面這段代碼是求三部分的和，經(jīng)過(guò)之前的學(xué)習(xí)應(yīng)該很容易知道，第一部分的時(shí)間復(fù)雜度是 O(n)，第二部分的時(shí)間復(fù)雜度是 O(n2)，第三部分是 O(n3)。

正常來(lái)講，這段代碼的 T(n) = O(n) + O(n2) + O(n3)，按照我們?nèi)　爸鲗?dǎo)”部分，顯然前面兩個(gè)小弟都應(yīng)該直接 pass，最終 T(n) = O(n3)。

通過(guò)這幾個(gè)例子，聰明的小婊貝們肯定會(huì)發(fā)現(xiàn)，對(duì)于時(shí)間復(fù)雜度分析來(lái)說(shuō)，只要找起“主導(dǎo)”作用的部分代碼即可，這個(gè)主導(dǎo)就是最高的那個(gè)復(fù)雜度，也就是執(zhí)行次數(shù)最多的那部分 n 的量級(jí)。

剩下的就是多加練習(xí)，有意識(shí)的多去想多去練，就可以和我一樣 帥氣 穩(wěn)啦。

這里推薦兩個(gè)比較好的資料，一份是筆記，一份最優(yōu)解，兩者加起來(lái)無(wú)敵。
兩個(gè)月斬獲 70k star，前字節(jié)大神刷題筆記
清華學(xué)霸的刷題筆記(leetcode最優(yōu)解)

常見時(shí)間復(fù)雜度

算法學(xué)習(xí)過(guò)程中，我們會(huì)遇到各種各樣的時(shí)間復(fù)雜度，但縱使你代碼七十二變，幾乎也逃不過(guò)下面這幾種常見的時(shí)間復(fù)雜度。

在這里插入圖片描述

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

下面主要來(lái)看剩下幾種最常見的時(shí)間復(fù)雜度。

O(1)

O(1) 是常數(shù)時(shí)間復(fù)雜度。

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

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

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

因?yàn)?strong>無(wú)論 n 等于多少，對(duì)于它們每行代碼來(lái)說(shuō)還是只是執(zhí)行了一次，代碼的執(zhí)行時(shí)間不隨 n 的變化而變化。

O(logn)

O(logn) 是對(duì)數(shù)時(shí)間復(fù)雜度。首先我們來(lái)看一段代碼：

dogegg = 1

while dogegg < n:
    dogegg = dogegg * 2

根據(jù)之前講的，我們先找“主導(dǎo)”，在這主導(dǎo)就是第 4 行代碼，只要算出它的時(shí)間復(fù)雜度，總的時(shí)間復(fù)雜度就知道了。

其實(shí)很簡(jiǎn)單，上面的代碼翻譯一下就是初始化 dogegg = 1， 乘上多少個(gè) 2 以后會(huì) ≥ n。

假設(shè)需要 x 個(gè)，那么相當(dāng)于求：

即：

image.png

所以上述代碼的時(shí)間復(fù)雜度應(yīng)該為 O(log2n)。

但是對(duì)于對(duì)數(shù)復(fù)雜度來(lái)說(shuō)，不管你是以 2、3 為底，還是以 10 為底，通通記作 O(logn)，這是為什么呢？

這就要從對(duì)數(shù)的換底公式說(shuō)起。

根據(jù)換底公式，log2n 可以寫成：

對(duì)于時(shí)間復(fù)雜度來(lái)說(shuō)：

所以在對(duì)數(shù)時(shí)間復(fù)雜度中我們就忽略了底，直接用 O(logn) 來(lái)表示對(duì)數(shù)時(shí)間復(fù)雜度。

O(nlogn)

O(nlogn)，真的是很常見的時(shí)間復(fù)雜度，像后面會(huì)學(xué)到的快速排序、歸并排序的時(shí)間復(fù)雜度都是 O(nlogn)。

如果只是簡(jiǎn)單看的話是在 logn 外面套了層 for 循環(huán)，比如像下面這段代碼：

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

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

當(dāng)然像上面這種 stupid 代碼一般人不會(huì)寫，我也只是舉個(gè)例子給大家看，我是狗蛋，大家千萬(wàn)不要以為我是傻狗。

最好情況、最壞情況和平均情況時(shí)間復(fù)雜度

除了數(shù)據(jù)集規(guī)模影響算法的運(yùn)行時(shí)間外，“數(shù)據(jù)的具體情況”也會(huì)影響到運(yùn)行時(shí)間。

我們來(lái)看這么一段代碼：

def find_word(lst, word):

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

    return flag

上面這段簡(jiǎn)單代碼是求變量 word 在列表 lst 中出現(xiàn)的位置，我用這段來(lái)解釋“數(shù)據(jù)的具體情況”是什么意思。

變量 word 可能出現(xiàn)在列表 lst 的任意位置，假設(shè) a = ['a', 'b', 'c', 'd']：

• 當(dāng) word = 'a' 時(shí)，正好是列表 lst 的第 1 個(gè)，后面的不需要再遍歷，那么本情況下的時(shí)間復(fù)雜度是 O(1)。

• 當(dāng) word = 'd' 或者 word = 'e' 時(shí)，這兩種情況是整個(gè)列表全部遍歷完，那么這些情況下的時(shí)間復(fù)雜度是 O(n)。

這就是數(shù)據(jù)的具體情況不同，代碼的時(shí)間復(fù)雜度不同。

根據(jù)不同情況，我們有了最好情況時(shí)間復(fù)雜度、最壞情況時(shí)間復(fù)雜度和平均情況時(shí)間復(fù)雜度這 3 個(gè)概念。

最好情況時(shí)間復(fù)雜度

最好情況就是在最理想的情況下，代碼的時(shí)間復(fù)雜度。對(duì)應(yīng)上例變量 word 正好是列表 lst 的第 1 個(gè)，這個(gè)時(shí)候?qū)?yīng)的時(shí)間復(fù)雜度 O(1) 就是這段代碼的最好情況時(shí)間復(fù)雜度。

最壞情況時(shí)間復(fù)雜度

最壞情況就是在最差的情況下，代碼的時(shí)間復(fù)雜度。對(duì)應(yīng)上例變量 word 正好是列表 lst 的最后一個(gè)，或者 word 不存在于列表 lst，這個(gè)時(shí)候?qū)?yīng)的時(shí)間復(fù)雜度 O(n) 是這段代碼的最壞情況時(shí)間復(fù)雜度。

平均情況時(shí)間復(fù)雜度

大多數(shù)情況下，代碼的執(zhí)行情況都是介于最好情況和最壞情況之間，所以又出現(xiàn)了平均情況時(shí)間復(fù)雜度。

那怎么計(jì)算平均時(shí)間復(fù)雜度呢？這個(gè)說(shuō)起來(lái)有點(diǎn)復(fù)雜，需要用到概率論的知識(shí)。

在這里我還是用上面的例子來(lái)講，因?yàn)橹皇呛?jiǎn)單的科普一下，為了方便計(jì)算，我假設(shè)的會(huì)有點(diǎn)隨意：

• 從大的方面來(lái)看，查找變量 x 在列表 lst 中的位置有兩種情況：在或者不在。假設(shè)變量 x 在或者不在列表 lst 中的概率都為 1/2。

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

每個(gè)出現(xiàn)的概率（即權(quán)重）知道了，所以平均時(shí)間復(fù)雜度為：

是不是看著有點(diǎn)眼熟，這就是我們都學(xué)過(guò)的加權(quán)平均值。

什么，沒(méi)學(xué)過(guò)？問(wèn)題不大。<font color=#ed5736>加權(quán)平均值</font>就是將各數(shù)值乘以相應(yīng)的權(quán)數(shù)，然后加總求和得到總體值，再除以總的單位數(shù)。

所以最終的平均時(shí)間復(fù)雜度就為：

臭寶：又是最好，又是最壞，又是平均的，這么多到底用哪個(gè)呀？
蛋蛋：這個(gè)還用問(wèn)？當(dāng)然是選擇最壞情況時(shí)間復(fù)雜度啊！

最好情況，反應(yīng)最理想的情況，怎么可能天上天天掉餡餅，沒(méi)啥參考價(jià)值。

平均情況，這倒是能反映算法的全面情況，但是一般“全面”，就和什么都沒(méi)說(shuō)一樣，也沒(méi)啥參考價(jià)值。

最壞情況，干啥事情都要考慮最壞的結(jié)果，因?yàn)樽顗牡慕Y(jié)果提供了一種保障，觸底的保障，保障代碼的運(yùn)行時(shí)間這個(gè)就是最差的，不會(huì)有比它還差的。

所以，不需要糾結(jié)各種情況，算時(shí)間復(fù)雜度就算最壞的那個(gè)時(shí)間復(fù)雜度即可。

空間復(fù)雜度

空間復(fù)雜度相較于時(shí)間復(fù)雜度來(lái)說(shuō)，比較簡(jiǎn)單，需要掌握的內(nèi)容不多。

空間復(fù)雜度和時(shí)間復(fù)雜度一樣，反映的也是一種趨勢(shì)，只不過(guò)這種趨勢(shì)是代碼運(yùn)行過(guò)程中臨時(shí)變量占用的內(nèi)存空間。

臭寶：為什么是“臨時(shí)”咧？
蛋蛋：這就要從代碼在計(jì)算機(jī)中的運(yùn)行說(shuō)起啦。

代碼在計(jì)算機(jī)中的運(yùn)行所占用的存儲(chǔ)空間吶，主要分為 3 部分：

• 代碼本身所占用的
• 輸入數(shù)據(jù)所占用的
• 臨時(shí)變量所占用的

前面兩個(gè)部分是本身就要占這些空間，與代碼的性能無(wú)關(guān)，所以我們<font color=#ed5736>在衡量代碼的空間復(fù)雜度的時(shí)候，只關(guān)心運(yùn)行過(guò)程中臨時(shí)占用的內(nèi)存空間。</font>

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

在這同樣 n 作為數(shù)據(jù)集大小，f(n) 指的是規(guī)模 n 所占存儲(chǔ)空間的函數(shù)。

空間復(fù)雜度分析

下面我們用一段簡(jiǎn)單代碼來(lái)學(xué)習(xí)下如何分析空間復(fù)雜度。

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

    return sum

上述代碼是求列表 lst 的所有元素之和，根據(jù)之前說(shuō)的，只計(jì)算臨時(shí)變量所占用的內(nèi)存空間。

形參 lst 所占的空間不計(jì)，那么剩下的臨時(shí)變量只有 sum 和 i，sum 是存儲(chǔ)和，是常數(shù)階，i 是存儲(chǔ)元素位置，也是常數(shù)階，它倆所分配的空間和規(guī)模 n 都沒(méi)有關(guān)系，所以整段代碼的空間復(fù)雜度 S(n) = O(1)。

常見空間復(fù)雜度

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

O(n)

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

    return lst

上面這段傻傻的代碼有兩個(gè)臨時(shí)變量 lst 和 i。

其中 lst 是被創(chuàng)建的一個(gè)空列表，這個(gè)列表占用的內(nèi)存隨著 for 循環(huán)的增加而增加，最大到 n，所以 lst 的空間復(fù)雜度為 O(n)，i 是存儲(chǔ)元素位置的常數(shù)階，與規(guī)模 n 無(wú)關(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)建了一個(gè)二維數(shù)組 lst，一維 lst1 占用 n，二維 lst2 占用 n2，所以最終這段代碼的空間復(fù)雜度為 O(n2)。

到這里，復(fù)雜度分析就全部講完啦，只要臭寶們認(rèn)真看完這篇文章，相信會(huì)對(duì)復(fù)雜度分析有個(gè)基本的認(rèn)識(shí)。復(fù)雜度分析本身不難，只要多加練習(xí)，平時(shí)寫代碼的時(shí)候有意識(shí)的多想估算一下自己的代碼，感覺就會(huì)慢慢來(lái)啦。

這是玩轉(zhuǎn)數(shù)據(jù)結(jié)構(gòu)與算法的第一篇，寫完真心不太容易，希望開了個(gè)好頭。碼字不易，臭寶們多多支持呀，么么噠。

我們下次見～