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

今天這篇文章主要說下如何分析、統(tǒng)計(jì)算法的執(zhí)行效率、資源消耗
我們知道數(shù)據(jù)結(jié)構(gòu)和算法本質(zhì)上解決的是 「快」和 「省」的問題歇终，那就是如何在占用更少資源的情況下更高效的執(zhí)行算法帆喇。這就是今天我們要說到的 時(shí)間復(fù)雜度與空間復(fù)雜度卫病。只要講到數(shù)據(jù)結(jié)構(gòu)和算法油啤，就一定離不開時(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ù)雜度分析

有些朋友可能會有些疑惑冗锁，我把代碼跑一遍，通過統(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)書籍還給這種統(tǒng)計(jì)方法起了一個(gè)名字堪澎，叫 事后統(tǒng)計(jì)法擂错。但是，這種統(tǒng)計(jì)方法存在著一些局限性

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

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

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

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

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

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

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

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

下面我們來看一段代碼绒瘦，該代碼塊主要實(shí)現(xiàn)的功能是計(jì)算 1,2,3......n 的累加和称簿，現(xiàn)在，一起來估算下這段代碼的執(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「福可以看出來骄蝇，所有代碼的執(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 的具體值虑鼎，但是通過上面兩段代碼執(zhí)行時(shí)間的推導(dǎo)過程，我們得到一個(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ī)模增長的變化趨勢，所以世澜，也叫 漸進(jìn)時(shí)間復(fù)雜度(asymptotic time complexity),簡稱 時(shí)間復(fù)雜度独旷。

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

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

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

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

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

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

大 O 時(shí)間復(fù)雜度表示法只是表示一段代碼的變化趨勢。我們通常會忽略公式中的 常量低飒、系數(shù)许昨、低階，所以褥赊，我們在分析一個(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 的大小沒有關(guān)系速那，對于時(shí)間復(fù)雜度并沒有影響。第 3尿背、4 行是執(zhí)行次數(shù)最多的端仰，所以我們重點(diǎn)關(guān)注這塊代碼，通過上面的介紹田藐，這兩行代碼都被執(zhí)行了 n 次荔烧，所以總的時(shí)間復(fù)雜度就是 O(n)

加法法則：總復(fù)雜度等于量級最大的那段代碼的復(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)在我們來看下這三段代碼的時(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 無關(guān)撮执，是一個(gè)常量級的執(zhí)行時(shí)間，當(dāng) n 無限大的時(shí)候舷丹，就可以忽略抒钱。盡管對代碼的執(zhí)行時(shí)間會有很大影響，但是回到時(shí)間復(fù)雜度的概念來講颜凯，它表示的是一個(gè)算法的執(zhí)行效率與數(shù)據(jù)規(guī)模增長的變化趨勢谋币，所以不管常量的執(zhí)行時(shí)間有多大，我們都可以把它忽略掉症概，因?yàn)樗旧韺υ鲩L趨勢并沒有影響
  • 第二段代碼和第三段代碼的時(shí)間復(fù)雜度分別是：O(n)蕾额、O(n^2)
    綜合這三段代碼的時(shí)間復(fù)雜度，我們?nèi)∑渲凶畲蟮牧考壉顺恰Ｋ宰绲厦孢@段代碼總的時(shí)間復(fù)雜度為 T(n) = O(n^2)。也就是說募壕，總的時(shí)間復(fù)雜度就等于量級最大的那段代碼的時(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))
也就是說舱馅，假設(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è)簡單的操作习柠，那么第 4 行代碼的時(shí)間復(fù)雜度就是匀谣，T1(n) = O(n)。但是第 5-8 行代碼不是一個(gè)簡單的操作资溃，它的時(shí)間復(fù)雜度是 T2(n) = O(n)武翎，所以，整段代碼的時(shí)間復(fù)雜度就是：
T(n) = T1(n) * T2(n) = O(n) * O(n) = O(n^2)

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

雖然代碼千差萬別溶锭，但是常見的復(fù)雜度量級并不多宝恶，下面我們將常見的幾種復(fù)雜度量級列舉出來，這些復(fù)雜度量級幾乎涵蓋了日常開發(fā)中接觸到的所有代碼的復(fù)雜度量級：

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

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

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

我們主要看幾種常見的多項(xiàng)式時(shí)間復(fù)雜度
1.常量階 O(1)
首先我們必須要明確一個(gè)概念，O(1) 只是常量級時(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 的增大而增長，這樣代碼的時(shí)間復(fù)雜度我們都記做 O(1)需频《⊙郏或者說，一般情況下昭殉，只要代碼中不存在循環(huán)語句苞七、遞歸語句，即使代碼中存在成千上萬的代碼挪丢，其時(shí)間復(fù)雜度也是 O(1)
2.對數(shù)時(shí)間復(fù)雜度和線性對數(shù)時(shí)間復(fù)雜度 O(logn)蹂风、O(nlogn)
對數(shù)階時(shí)間復(fù)雜度非常常見，同時(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 開始取值，每循環(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)過計(jì)算 x = log2n狼渊，所以，這段代碼的時(shí)間復(fù)雜度就是 O(log2n)

換底公式：logab = logcb/logca

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

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

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

我們知道對數(shù)之間是可以互相轉(zhuǎn)換的氯析，log3n = log32 * log 2n亏较，所以，O(log3n) = O(log32 * log2n) = O(C * log2n) 掩缓，其中 C = log32 是一個(gè)常量雪情。基于我們前面介紹的你辣，使用大 O 時(shí)間復(fù)雜度表示法的時(shí)候 常量巡通、系數(shù)、階數(shù) 都可以忽略不計(jì)舍哄，即 O(Cf(n)) = O(f(n))宴凉。所以，O(log3n) = O(log2n),因此表悬，在對數(shù)階時(shí)間復(fù)雜度表示方法中弥锄，我們可以忽略對數(shù)的 底，統(tǒng)一表示為 O(logn)

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

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

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

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

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

第 1 行代碼會執(zhí)行 n + 1 次，第 2捏顺、3 行代碼會分別執(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)
我們再來介紹一種和前面都不一樣的時(shí)間復(fù)雜度主巍，通過上面的介紹我們知道 大 O 時(shí)間復(fù)雜度表示法并不真正表示算法的執(zhí)行時(shí)間冠息，只是表示算法的執(zhí)行時(shí)間隨著數(shù)據(jù)規(guī)模 n 的增大的增長趨勢，在這里我們知道代碼的復(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ù)雜度等于量級最大的那段代碼的時(shí)間復(fù)雜度逛艰，從這段代碼中我們可以看出，m 和 n 表示兩個(gè)數(shù)據(jù)規(guī)模搞旭。我們無法評估出 m 和 n 誰的量級大散怖，所以我們在估算時(shí)間復(fù)雜度的時(shí)間，就不能再簡單的利用加法法則肄渗，省略掉其中一個(gè)镇眷。所以，上面代碼的時(shí)間復(fù)雜度就是 O(m + n)

針對數(shù)據(jù)規(guī)模有多個(gè)控制的時(shí)候翎嫡，原來的加法法則就不正確了欠动，我們需要將加法法則改為：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ī)模之間的增長關(guān)系具伍。類比一下，空間復(fù)雜度的全稱就是 漸進(jìn)空間復(fù)雜度硝桩，表示算法的存儲空間與數(shù)據(jù)規(guī)模之間的增長關(guān)系

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

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

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

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

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

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

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

空間復(fù)雜度 O(n)
int[] m = newint[n]
for(i=1; i <= n; ++i) {
   j = i;
   j++;
}

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

總結(jié)

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

常見的復(fù)雜度并不多致板，從低階到高階有：O(1)、O(logn)咏窿、O(n)斟或、O(nlogn)、O(n^2)

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末集嵌，一起剝皮案震驚了整個(gè)濱河市萝挤，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌根欧，老刑警劉巖怜珍，帶你破解...
    沈念sama閱讀 218,682評論 6贊 507
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異凤粗，居然都是意外死亡酥泛，警方通過查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,277評論 3贊 395
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門嫌拣，熙熙樓的掌柜王于貴愁眉苦臉地迎上來柔袁，“玉大人，你說我怎么就攤上這事异逐〈匪鳎” “怎么了？”我有些...
    開封第一講書人閱讀 165,083評論 0贊 355
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵灰瞻，是天一觀的道長腥例。 經(jīng)常有香客問我，道長酝润，這世上最難降的妖魔是什么燎竖？ 我笑而不...
    開封第一講書人閱讀 58,763評論 1贊 295
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任，我火速辦了婚禮袍祖，結(jié)果婚禮上底瓣，老公的妹妹穿的比我還像新娘。我一直安慰自己，他們只是感情好捐凭，可當(dāng)我...
    茶點(diǎn)故事閱讀 67,785評論 6贊 392
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布拨扶。 她就那樣靜靜地躺著，像睡著了一般茁肠。 火紅的嫁衣襯著肌膚如雪患民。 梳的紋絲不亂的頭發(fā)上，一...
    開封第一講書人閱讀 51,624評論 1贊 305
  • 城市分裂傳說
    那天垦梆，我揣著相機(jī)與錄音匹颤，去河邊找鬼。 笑死托猩，一個(gè)胖子當(dāng)著我的面吹牛印蓖，可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播京腥，決...
    沈念sama閱讀 40,358評論 3贊 418
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼赦肃，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了公浪？” 一聲冷哼從身側(cè)響起他宛，我...
    開封第一講書人閱讀 39,261評論 0贊 276
  • 萬榮殺人案實(shí)錄
    序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎欠气，沒想到半個(gè)月后厅各，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
    沈念sama閱讀 45,722評論 1贊 315
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡预柒，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,900評論 3贊 336
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年队塘，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片卫旱。...
    茶點(diǎn)故事閱讀 40,030評論 1贊 350
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡人灼，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出顾翼，到底是詐尸還是另有隱情投放，我是刑警寧澤，帶...
    沈念sama閱讀 35,737評論 5贊 346
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布适贸，位于F島的核電站灸芳，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏拜姿。R本人自食惡果不足惜烙样，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,360評論 3贊 330
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望蕊肥。 院中可真熱鬧谒获，春花似錦蛤肌、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,941評論 0贊 22
  • 一樁弒父案裸准，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至赔硫，卻和暖如春炒俱，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背爪膊。 一陣腳步聲響...
    開封第一講書人閱讀 33,057評論 1贊 270
  • 情欲美人皮
    我被黑心中介騙來泰國打工权悟， 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人推盛。 一個(gè)月前我還...
    沈念sama閱讀 48,237評論 3贊 371
  • 代替公主和親
    正文 我出身青樓峦阁，卻偏偏與公主長得像，于是被迫代替她去往敵國和親耘成。 傳聞我的和親對象是個(gè)殘疾皇子拇派，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,976評論 2贊 355