今天這篇文章主要說(shuō)下如何分析、統(tǒng)計(jì)算法的執(zhí)行效率、資源消耗
我們知道數(shù)據(jù)結(jié)構(gòu)和算法本質(zhì)上解決的是 「快」和 「省」的問(wèn)題，那就是如何在占用更少資源的情況下更高效的執(zhí)行算法。這就是今天我們要說(shuō)到的 時(shí)間復(fù)雜度與空間復(fù)雜度。只要講到數(shù)據(jù)結(jié)構(gòu)和算法，就一定離不開(kāi)時(shí)間復(fù)雜度與空間復(fù)雜度。復(fù)雜度分析是整個(gè)算法學(xué)習(xí)的精髓，只要掌握了它，數(shù)據(jù)結(jié)構(gòu)和算法的內(nèi)容基本上就掌握了一半。復(fù)雜度分析 就像是內(nèi)功心法，如果我們只掌握了數(shù)據(jù)結(jié)構(gòu)和算法用法、特點(diǎn)，那我們只是學(xué)到上乘武功的招式，我們知道上乘武功還需要搭配牛逼的內(nèi)功心法才能發(fā)揮它的能力

為什么需要復(fù)雜度分析

有些朋友可能會(huì)有些疑惑，我把代碼跑一遍，通過(guò)統(tǒng)計(jì)、監(jiān)控，就能得到算法執(zhí)行的時(shí)間和占用的內(nèi)存大小。為什么還要做時(shí)間、空間復(fù)雜度分析呢?這種分析方法能比我實(shí)實(shí)在在跑一遍得到的數(shù)據(jù)還要準(zhǔn)確嗎?

這種統(tǒng)計(jì)方法不是不行，也能得出相關(guān)算法的執(zhí)行時(shí)間和占用內(nèi)存大小，很多數(shù)據(jù)結(jié)構(gòu)和算法的相關(guān)書(shū)籍還給這種統(tǒng)計(jì)方法起了一個(gè)名字，叫 事后統(tǒng)計(jì)法。但是，這種統(tǒng)計(jì)方法存在著一些局限性

測(cè)試結(jié)果非常依賴測(cè)試環(huán)境

測(cè)試環(huán)境中硬件的不同會(huì)對(duì)測(cè)試結(jié)果有很大的影響。比如，我們拿同一段代碼，分別用 Intel Core i7 處理器和 Intel Core i3 處理器來(lái)運(yùn)行，不用說(shuō)，i7 處理器要比 i3 處理器的執(zhí)行速度要快得多

測(cè)試結(jié)果受數(shù)據(jù)規(guī)模的影響很大

我們拿排序算法舉個(gè)例子，對(duì)于同一個(gè)排序算法，待排序的數(shù)據(jù)有序度不一樣，排序的執(zhí)行時(shí)間就會(huì)有很大的差別
極端情況下，待排序的數(shù)據(jù)是有序的，那排序算法不需要做出任何操作，執(zhí)行時(shí)間就會(huì)非常短。除此之外，如果測(cè)試數(shù)據(jù)規(guī)模太小，測(cè)試結(jié)果可能就無(wú)法真實(shí)的反映出算法的性能

比如，對(duì)于小規(guī)模的數(shù)據(jù)排序，插入排序可能反倒要比快速排序要快

所以，我們需要一個(gè)不用具體的測(cè)試數(shù)據(jù)測(cè)試，就能粗略的估計(jì)算法執(zhí)行效率的方法。這就是下面要說(shuō)到的時(shí)間、空間復(fù)雜度分析方法

大 O 復(fù)雜度表示法

算法的執(zhí)行效率，簡(jiǎn)單的說(shuō)，就是算法執(zhí)行的時(shí)間。但是，如何不在運(yùn)行代碼的情況下就能估算出算法的執(zhí)行時(shí)間

下面我們來(lái)看一段代碼，該代碼塊主要實(shí)現(xiàn)的功能是計(jì)算 1,2,3......n 的累加和，現(xiàn)在，一起來(lái)估算下這段代碼的執(zhí)行時(shí)間

function cal($n) {
     $sum = 0;
     for($i = 1;$i < $n;$i++) {
           $sum += $i;
     }
     return $sum;
}

我們這里只是粗略的估算，所以假設(shè)每一行代碼執(zhí)行的時(shí)間都一樣，為 unit_time

在這個(gè)假設(shè)的基礎(chǔ)上，這段代碼的執(zhí)行時(shí)間是多少呢？

第 2 行代碼需要 1 個(gè) unit_time 的執(zhí)行時(shí)間，第 3、4 行代碼都已經(jīng)運(yùn)行了 n 遍，所以需要 2n * unit_time 的執(zhí)行時(shí)間，所以這段代碼總的執(zhí)行時(shí)間就是 (2n + 1) * unit_time?？梢钥闯鰜?lái)，所有代碼的執(zhí)行時(shí)間 T(n) 與每行代碼的執(zhí)行次數(shù)成正比

我們繼續(xù)分析下面這段代碼

function cal($n) {
     $sum = 0;
     for($i = 1;$i < $n;$i++) {
           for($j = 1;$j < $n;$j ++) {
                $sum = $sum + $i * $j;
           }
     }
     return $sum;
}

我們依然假設(shè)每一行代碼的執(zhí)行時(shí)間為 unit_time。那么這段代碼總的執(zhí)行時(shí)間是多少呢?

第 2 行代碼需要 1 個(gè) unit_time 的執(zhí)行時(shí)間，第 3 行代碼循環(huán)執(zhí)行了 n 遍，需要 n * unit_time 的執(zhí)行時(shí)間，第 4、5 行代碼循環(huán)執(zhí)行了 2n^2 遍，所以需要 2n^2 * unit_time 的執(zhí)行時(shí)間。所以，這段代碼總的執(zhí)行時(shí)間 T(n) = (2n^2 + n + 1) * unit_time

盡管我們不知道 unit_time 的具體值，但是通過(guò)上面兩段代碼執(zhí)行時(shí)間的推導(dǎo)過(guò)程，我們得到一個(gè)非常重要的規(guī)律，所有代碼的執(zhí)行時(shí)間 T(n) 與每行代碼執(zhí)行次數(shù) n 成正比

我們就可以把這個(gè)規(guī)律總結(jié)成一個(gè)公式

T(n) = O(f(n))

其中，T(n) 表示所有代碼總的執(zhí)行時(shí)間，n 表示代碼的執(zhí)行次數(shù)也可以表示數(shù)據(jù)規(guī)模的大小；f(n) 表示每行代碼執(zhí)行次數(shù)的總和。因?yàn)檫@是一個(gè)公式，所以使用 f(n) 表示，公式中的 O 表示代碼的執(zhí)行時(shí)間 T(n) 與 f(n)表達(dá)式成正比

所以，第一個(gè)例子中的 T(n) = O(2n + 1)，第二個(gè)例子中的 T(n) = O(2n^2 + n + 1)。這就是 大 O 時(shí)間復(fù)雜度表示法

大 O 時(shí)間復(fù)雜度表示法并不具體表示代碼真正的執(zhí)行時(shí)間，而是表示 代碼執(zhí)行時(shí)間隨數(shù)據(jù)規(guī)模增長(zhǎng)的變化趨勢(shì)，所以，也叫 漸進(jìn)時(shí)間復(fù)雜度(asymptotic time complexity),簡(jiǎn)稱 時(shí)間復(fù)雜度。

注意：時(shí)間復(fù)雜度表示的是變化趨勢(shì)，并不是真正的執(zhí)行時(shí)間

當(dāng) n 很大時(shí)，公式中的 常量、系數(shù)、低階 并不能影響到整體的變化趨勢(shì)，所以這些是可以忽略的，所以，用大 O 時(shí)間復(fù)雜度表示法表示上面兩個(gè)例子的時(shí)間復(fù)雜度，就可以表示為：

T(n) = O(n)
T(n) = O(n ^ 2)

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

通過(guò)上面的介紹我們已經(jīng)了解了大 O 時(shí)間復(fù)雜度表示法。接下來(lái)我們來(lái)看下如何分析一段代碼的時(shí)間復(fù)雜度?

只關(guān)注循環(huán)次數(shù)最多的一段代碼

大 O 時(shí)間復(fù)雜度表示法只是表示一段代碼的變化趨勢(shì)。我們通常會(huì)忽略公式中的 常量、系數(shù)、低階，所以，我們?cè)诜治鲆粋€(gè)算法的時(shí)間復(fù)雜度的時(shí)候，只需要關(guān)注循環(huán)次數(shù)最多的那一段代碼就可以了，如下：

function cal($n) {
     $sum = 0;
     for($i = 1;$i < $n;$i++) {
           $sum += $i;
     }
     return $sum;
}

這段代碼第 2 行的執(zhí)行時(shí)間是一個(gè)常量，與 n 的大小沒(méi)有關(guān)系，對(duì)于時(shí)間復(fù)雜度并沒(méi)有影響。第 3、4 行是執(zhí)行次數(shù)最多的，所以我們重點(diǎn)關(guān)注這塊代碼，通過(guò)上面的介紹，這兩行代碼都被執(zhí)行了 n 次，所以總的時(shí)間復(fù)雜度就是 O(n)

加法法則：總復(fù)雜度等于量級(jí)最大的那段代碼的復(fù)雜度

看下面這段代碼：

int cal(int n) {
   int sum_1 = 0;
   int p = 1;
   for (; p < 100; ++p) {
     sum_1 = sum_1 + p;
   }
 
   int sum_2 = 0;
   int q = 1;
   for (; q < n; ++q) {
     sum_2 = sum_2 + q;
   }
 
   int sum_3 = 0;
   int i = 1;
   int j = 1;
   for (; i <= n; ++i) {
     j = 1;
     for (; j <= n; ++j) {
       sum_3 = sum_3 +  i * j;
     }
   }
 
   return sum_1 + sum_2 + sum_3;
 }

這段代碼可以分為 3 部分，分別計(jì)算 sum_1、sum_2、sum_3。我們可以分別估算出每段代碼的時(shí)間復(fù)雜度，現(xiàn)在我們來(lái)看下這三段代碼的時(shí)間復(fù)雜度：

• 第一段代碼：第 2、3 行代碼都需要 1 個(gè) unit_time 的執(zhí)行時(shí)間，第 4、5 行代碼執(zhí)行了 2 * 100 次，故需要 2 * 100 * unit_time 的執(zhí)行時(shí)間，可以看到這段代碼的執(zhí)行時(shí)間是一個(gè)常量，與 n 無(wú)關(guān)，是一個(gè)常量級(jí)的執(zhí)行時(shí)間，當(dāng) n 無(wú)限大的時(shí)候，就可以忽略。盡管對(duì)代碼的執(zhí)行時(shí)間會(huì)有很大影響，但是回到時(shí)間復(fù)雜度的概念來(lái)講，它表示的是一個(gè)算法的執(zhí)行效率與數(shù)據(jù)規(guī)模增長(zhǎng)的變化趨勢(shì)，所以不管常量的執(zhí)行時(shí)間有多大，我們都可以把它忽略掉，因?yàn)樗旧韺?duì)增長(zhǎng)趨勢(shì)并沒(méi)有影響
• 第二段代碼和第三段代碼的時(shí)間復(fù)雜度分別是：O(n)、O(n^2)
  綜合這三段代碼的時(shí)間復(fù)雜度，我們?nèi)∑渲凶畲蟮牧考?jí)。所以，上面這段代碼總的時(shí)間復(fù)雜度為 T(n) = O(n^2)。也就是說(shuō)，總的時(shí)間復(fù)雜度就等于量級(jí)最大的那段代碼的時(shí)間復(fù)雜度。我們將這個(gè)規(guī)律抽象成公式就是：

T1(n) = O(f(n)),T2(n) = O(g(n)),T(n) = T1(n) + T2(n) = max(O(f(n)),O(g(n))) = O(max(f(n),g(n)))

乘法法則：嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積

如果 T1(n) = O(f(n)),T2(n) = O(g(n));那么，T(n) = T1(n) * T2(n) = O(f(n)) * O(g(n)) = O(f(n) * g(n))
也就是說(shuō)，假設(shè) T1(n) = O(n),T2(n) = O(n^2)，則：
T1(n) * T2(n) = O(n^3)
下面我們看一個(gè)具體的代碼：

int cal(int n) {
   int ret = 0;
   int i = 1;
   for(x=1; i <= n; x++){
       for(i = 1; i <= n; i++) {
           j = i;
           j++;
        }
    }
 }
 

分析這段代碼的時(shí)間復(fù)雜度。假設(shè)該段代碼的第 5-8 行是一個(gè)簡(jiǎn)單的操作，那么第 4 行代碼的時(shí)間復(fù)雜度就是，T1(n) = O(n)。但是第 5-8 行代碼不是一個(gè)簡(jiǎn)單的操作，它的時(shí)間復(fù)雜度是 T2(n) = O(n)，所以，整段代碼的時(shí)間復(fù)雜度就是：
T(n) = T1(n) * T2(n) = O(n) * O(n) = O(n^2)

幾種常見(jiàn)的時(shí)間復(fù)雜度實(shí)例

雖然代碼千差萬(wàn)別，但是常見(jiàn)的復(fù)雜度量級(jí)并不多，下面我們將常見(jiàn)的幾種復(fù)雜度量級(jí)列舉出來(lái)，這些復(fù)雜度量級(jí)幾乎涵蓋了日常開(kāi)發(fā)中接觸到的所有代碼的復(fù)雜度量級(jí)：

• 常量階 O(1)
• 對(duì)數(shù)階 O(logn)
• 線性階 O(n)
• 線性對(duì)數(shù)階 O(nlogn)
• 平方階 O(n^2)、立方階 O(n^3)......k 次方階 O(n^k)
• 指數(shù)階 O(2^n)
• 階乘階 O(n!)
  對(duì)于上面羅列的常見(jiàn)的復(fù)雜度量級(jí)我們可以粗略的分為兩類：多項(xiàng)式量級(jí) 和 非多項(xiàng)式量級(jí)。其中，非多項(xiàng)式量級(jí)只有兩個(gè)：O(2^n) 和 O(n!)

多項(xiàng)式量級(jí)就是說(shuō)這個(gè)時(shí)間復(fù)雜度是以 n 作為底數(shù)，如：對(duì)數(shù)階 O(logn)、k 次方階 O(n^k)等
非多項(xiàng)式量級(jí)就是說(shuō)這個(gè)時(shí)間復(fù)雜度不是以n作為底數(shù)，如：指數(shù)階 O(2^n)、階乘階 O(n!)

當(dāng)數(shù)據(jù)規(guī)模 n 越來(lái)越大的時(shí)候，非多項(xiàng)式量級(jí)的算法執(zhí)行時(shí)間會(huì)急劇增加，所以，非多項(xiàng)式量級(jí)的算法其實(shí)是非常低效的算法，一般情況下，我們把非多項(xiàng)式量級(jí)的算法問(wèn)題成為 NP 問(wèn)題(Non-Deterministic Polynomial)-非確定多項(xiàng)式

我們主要看幾種常見(jiàn)的多項(xiàng)式時(shí)間復(fù)雜度
1.常量階 O(1)
首先我們必須要明確一個(gè)概念，O(1) 只是常量級(jí)時(shí)間復(fù)雜度的一種表示法，并不是指只執(zhí)行一行代碼。比如下面這段代碼，即使只有 3 行，它的時(shí)間復(fù)雜度也是 O(1)，并不是 O(3)

int a = 1;
int b = 2;
int c = 3;

只要代碼的執(zhí)行時(shí)間不隨著數(shù)據(jù)規(guī)模 n 的增大而增長(zhǎng)，這樣代碼的時(shí)間復(fù)雜度我們都記做 O(1)?；蛘哒f(shuō)，一般情況下，只要代碼中不存在循環(huán)語(yǔ)句、遞歸語(yǔ)句，即使代碼中存在成千上萬(wàn)的代碼，其時(shí)間復(fù)雜度也是 O(1)
2.對(duì)數(shù)時(shí)間復(fù)雜度和線性對(duì)數(shù)時(shí)間復(fù)雜度 O(logn)、O(nlogn)
對(duì)數(shù)階時(shí)間復(fù)雜度非常常見(jiàn)，同時(shí)也是最難分析的一種時(shí)間復(fù)雜度

i = 1;
while(i < n) {
   i = i * 2;
}

根據(jù)前面我們講的時(shí)間復(fù)雜度分析法 「只關(guān)注循環(huán)次數(shù)最多的一段代碼」，第三行代碼的循環(huán)次數(shù)最多。所以，我們只需要計(jì)算出這段代碼的執(zhí)行次數(shù)，就能知道這段代碼的時(shí)間復(fù)雜度

從上面代碼中可以看出，變量 i 的值從 1 開(kāi)始取值，每循環(huán)一次就乘以 2。當(dāng)大于 n 時(shí)，循環(huán)結(jié)束。這有點(diǎn)類似我們高中學(xué)習(xí)的等比數(shù)列，實(shí)際上，變量 i 的取值就是一個(gè)等比數(shù)列。如下所示：

2^0*2^1*2^2*2^3......2^x = n

所以，我們只需要知道 x 值是多少，就能知道這段代碼的執(zhí)行次數(shù)了。那么我們只需要計(jì)算 2^x = n 就行了，在這里經(jīng)過(guò)計(jì)算 x = log₂n，所以，這段代碼的時(shí)間復(fù)雜度就是 O(log₂n)

換底公式：log_ab = log_cb/log_ca

我們把上面那段代碼稍微改下，看下下面這段代碼的時(shí)間復(fù)雜度是多少？

i = 1;
while(i <= n) {
    i = i * 3;
}

同樣使用上面的分析方法可知，這段代碼的時(shí)間復(fù)雜度為 O(log₃n)
實(shí)際上，不管是以 2 為底、以 3 為底，還是以 10為底，我們都可以把所有對(duì)數(shù)階的時(shí)間復(fù)雜度都記為 O(logn)，為什么呢？

我們知道對(duì)數(shù)之間是可以互相轉(zhuǎn)換的，log₃n = log₃2 * log ₂n，所以，O(log₃n) = O(log₃2 * log₂n) = O(C * log₂n) ，其中 C = log₃2 是一個(gè)常量?；谖覀兦懊娼榻B的，使用大 O 時(shí)間復(fù)雜度表示法的時(shí)候 常量、系數(shù)、階數(shù) 都可以忽略不計(jì)，即 O(Cf(n)) = O(f(n))。所以，O(log₃n) = O(log₂n),因此，在對(duì)數(shù)階時(shí)間復(fù)雜度表示方法中，我們可以忽略對(duì)數(shù)的 底，統(tǒng)一表示為 O(logn)

下面我們看下線性對(duì)數(shù)階 O(nlogn)，還記得上面我們介紹過(guò)的乘法法則嗎？嵌套代碼的時(shí)間復(fù)雜度等于嵌套內(nèi)外代碼時(shí)間復(fù)雜度的乘積。如果一段代碼的時(shí)間復(fù)雜度是 O(logn)，我們將這段代碼執(zhí)行 遍，時(shí)間復(fù)雜度就是 O(nlogn) 了。*線性對(duì)數(shù)階 O(nlogn) *也是一種非常常見(jiàn)的算法時(shí)間復(fù)雜度

如下代碼時(shí)間復(fù)雜度就是 O(nlogn)，內(nèi)部 while 循環(huán)的時(shí)間復(fù)雜度是 O(logn),被外層 for 循環(huán)包起來(lái)，所以就是 O(nlogn)

for(m = 1;m < n;m++) {
    i = 1;
    while(i < n) {
         i = i * 2;
    }
}

3.線性階
看下面這段代碼會(huì)執(zhí)行多少次

for(i = 1;i <= n;i++) {
     j = i;
     j++
}

第 1 行代碼會(huì)執(zhí)行 n + 1 次，第 2、3 行代碼會(huì)分別執(zhí)行 n 次，總的執(zhí)行時(shí)間是 3n + 1次，根據(jù)前面我們介紹的 大 O 時(shí)間復(fù)雜度表示法 可知，它的時(shí)間復(fù)雜度是 O(n)

4.平方階(O(n^2))

for(x=1; i <= n; x++){
   for(i = 1; i <= n; i++) {
       j = i;
       j++;
    }
}

把時(shí)間復(fù)雜度為 O(n) 的代碼再嵌套循環(huán)一次，它的時(shí)間復(fù)雜度就是 O(n^2)
立方階 O(n^3)、k 次方階 O(n^k)
5.O(m + n)、O(m * n)
我們?cè)賮?lái)介紹一種和前面都不一樣的時(shí)間復(fù)雜度，通過(guò)上面的介紹我們知道 大 O 時(shí)間復(fù)雜度表示法并不真正表示算法的執(zhí)行時(shí)間，只是表示算法的執(zhí)行時(shí)間隨著數(shù)據(jù)規(guī)模 n 的增大的增長(zhǎng)趨勢(shì)，在這里我們知道代碼的復(fù)雜度只取決于一個(gè)數(shù)據(jù)規(guī)模 n,那么當(dāng)數(shù)據(jù)規(guī)模有兩個(gè)決定時(shí)又是怎么樣的呢？

int cal(int m, int n) {
  int sum_1 = 0;
  int i = 1;
  for (; i < m; ++i) {
    sum_1 = sum_1 + i;
  }
 
  int sum_2 = 0;
  int j = 1;
  for (; j < n; ++j) {
    sum_2 = sum_2 + j;
  }
 
  return sum_1 + sum_2;
}

根據(jù)前面介紹的 乘法法則：總的時(shí)間復(fù)雜度等于量級(jí)最大的那段代碼的時(shí)間復(fù)雜度，從這段代碼中我們可以看出，m 和 n 表示兩個(gè)數(shù)據(jù)規(guī)模。我們無(wú)法評(píng)估出 m 和 n 誰(shuí)的量級(jí)大，所以我們?cè)诠浪銜r(shí)間復(fù)雜度的時(shí)間，就不能再簡(jiǎn)單的利用加法法則，省略掉其中一個(gè)。所以，上面代碼的時(shí)間復(fù)雜度就是 O(m + n)

針對(duì)數(shù)據(jù)規(guī)模有多個(gè)控制的時(shí)候，原來(lái)的加法法則就不正確了，我們需要將加法法則改為：T1(m) + T2(n) = O(f(m) + g(n))。但是乘法法則繼續(xù)有效：T1(m) * T2(n) = O(f(m) * g(n))

空間復(fù)雜度分析

時(shí)間復(fù)雜度的全稱是 漸進(jìn)時(shí)間復(fù)雜度，表示算法的執(zhí)行時(shí)間與數(shù)據(jù)規(guī)模之間的增長(zhǎng)關(guān)系。類比一下，空間復(fù)雜度的全稱就是 漸進(jìn)空間復(fù)雜度，表示算法的存儲(chǔ)空間與數(shù)據(jù)規(guī)模之間的增長(zhǎng)關(guān)系

void print(int n) {
  int i = 0;
  int[] a = newint[n];
  for (i; i <n; ++i) {
    a[i] = i * i;
  }
}

通過(guò)上面這段代碼我們可以看到，第 2 行代碼中，我們申請(qǐng)了一個(gè)空間存儲(chǔ)變量 i，但是它是常量階的，跟數(shù)據(jù)規(guī)模 n 沒(méi)有關(guān)系，所以我們可以忽略不計(jì)。第 3 行代碼申請(qǐng)了一個(gè)大小為 n 的 int 類型的數(shù)組，除此之外，剩下的代碼都沒(méi)有占用更多的空間，所以，整段代碼的空間復(fù)雜度就是 O(n)

我們常見(jiàn)的空間復(fù)雜度就是 O(1)、O(n)、O(n^2)，像 O(logn)、O(nlogn) 這樣的對(duì)數(shù)階空間復(fù)雜度平時(shí)都用不到。而且空間復(fù)雜度分析要比時(shí)間復(fù)雜度分析要簡(jiǎn)單很多,下面我們介紹下平時(shí)使用的比較多的空間復(fù)雜度

空間復(fù)雜度 O(1)

如果算法執(zhí)行所需要的存儲(chǔ)空間不隨著某個(gè)變量 n 的大小而變化，即此算法空間復(fù)雜度為一個(gè)常量，可表示為 O(1)

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

上述代碼中 i、j 變量所分配的內(nèi)存空間都不會(huì)隨著處理數(shù)據(jù)量的變化而變化，因此，它的空間復(fù)雜度是 O(1)

空間復(fù)雜度 O(n)

int[] m = newint[n]
for(i=1; i <= n; ++i) {
   j = i;
   j++;
}

這段代碼中第 1 行申請(qǐng)了大小為 n 的 int 類型數(shù)組，后面雖然有循環(huán)，但是沒(méi)有再分配新的內(nèi)存空間，因此，這段代碼的空間復(fù)雜度主要看第一行即可

總結(jié)

復(fù)雜度也叫漸進(jìn)復(fù)雜度，包括時(shí)間復(fù)雜度、空間復(fù)雜度，用來(lái)分析算法執(zhí)行效率與數(shù)據(jù)規(guī)模之間的增長(zhǎng)關(guān)系，可以粗略的表示，越高階復(fù)雜度的算法，執(zhí)行效率越低

常見(jiàn)的復(fù)雜度并不多，從低階到高階有：O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)