[[430592]]

如果提到性能分析，你會(huì)想到什么呢?

可以做耗時(shí)分析、內(nèi)存占用的的分析?？梢杂?chrome devtools 的 Profiler，包括 performance 和 memory，分別拿到耗時(shí)和內(nèi)存占用的數(shù)據(jù)，而且還可以用火焰圖做可視化分析。

比如 performance，你可以看到每個(gè)函數(shù)的耗時(shí)，通過簡單的加減法，就能算出是哪個(gè)函數(shù)耗時(shí)多，然后去優(yōu)化。

而且，你可以勾選 memory，顯示堆內(nèi)存的變化，可以知道是哪個(gè)函數(shù)導(dǎo)致的內(nèi)存增多，然后去優(yōu)化。

當(dāng)然，你也可以單獨(dú)分析 memory 的 timeline，錄制一段時(shí)間的內(nèi)存占用情況，然后看這時(shí)候的內(nèi)存中有哪些對(duì)象，這樣比只知道大小更精確一些。

總之，我們可以通過調(diào)試工具的 Profiler 來看到內(nèi)存和耗時(shí)，然后關(guān)聯(lián)到具體的函數(shù)，之后著手去優(yōu)化。

但是，這些都是代碼跑起來才能統(tǒng)計(jì)的，而且與機(jī)器、不同的輸入數(shù)據(jù)等強(qiáng)相關(guān)。

如果換一臺(tái)機(jī)器，數(shù)據(jù)就是另一個(gè)樣子了。這也是為啥測試的時(shí)候要用各種機(jī)器測一遍。

那如果想代碼不運(yùn)行就能估算出具體時(shí)間和內(nèi)存占用大小，有什么思路么?

這就是復(fù)雜度分析技術(shù)做的事情了。

這篇文章我們來學(xué)下復(fù)雜度分析是如何估算時(shí)間的。

復(fù)雜度分析的幾個(gè)基礎(chǔ)

什么是 1，什么是 n

如果有這樣一行代碼：

const name = 'guang'; 

耗時(shí)多少，內(nèi)存多少?

你可能說得跑跑看，可能耗時(shí) 1ms，內(nèi)存 4 bytes，也可能耗時(shí) 2ms，內(nèi)存 8bytes 等等，不同的機(jī)器和運(yùn)行環(huán)境都會(huì)有不同。

但我們都把它作為 1 ，這個(gè) 1 不是 ms，不是 byte，只是說是一個(gè)耗時(shí)/內(nèi)存占用的基本單元，也就是復(fù)雜度是 1。

那這樣的代碼呢?

function calc(n) { 
    for(let i = 0; i < n; i ++) { 
        //... 
    } 
} 

具體的數(shù)值隨著 n 的增大而增大，復(fù)雜度是 n。

我們分析復(fù)雜度的時(shí)候，不會(huì)分析具體的耗時(shí)和內(nèi)存占用，而是以語句作為復(fù)雜度的單元，也就是 1，隨著輸入的數(shù)據(jù)規(guī)模 n 而變化的復(fù)雜度作為 n。

漸進(jìn)的時(shí)候，常數(shù)可省略

我們知道了 1 和 n，就可以計(jì)算這些復(fù)雜度了：

function func(n) { 
    const a = 1; 
    const b = 2; 
     
    for (let i = 0; i < n; i ++) { 
       //... 
    } 
} 

這里面有兩條語句，復(fù)雜度是 1 + 1，一個(gè)循環(huán) n 次的語句，復(fù)雜度是 n，所以總復(fù)雜度是 2 + n。

復(fù)雜度(func) = 2 + n 

當(dāng)這個(gè) n 逐漸變大的時(shí)候，比如 n 變成了 10000000，那這個(gè) 2 就可以忽略不計(jì)了。

也就是

復(fù)雜度(func) =  O(n) 

這個(gè) O 是漸進(jìn)復(fù)雜度的意思，也就是漸漸的增大的時(shí)候的復(fù)雜度。

有的同學(xué)說，這里是 2，所以可以省略，如果這里有 100000 條呢?是不是就不能省略了?

其實(shí)也會(huì)省略，因?yàn)椴还芏啻?，它的?fù)雜度總是一個(gè)常數(shù)，是固定的，不會(huì)變化，所以不用分析進(jìn)去，估算出的耗時(shí)或者內(nèi)存占用加上它那固定的部分就可以了。而變化的部分才需要分析。

當(dāng)我們計(jì)算漸進(jìn)復(fù)雜度 O 的時(shí)候，常數(shù)會(huì)省略掉，因?yàn)樗枪潭ǖ?，不?huì)變，而我們只分析變化的部分，也就是與 n 有關(guān)的部分。

多個(gè)變化的輸入數(shù)據(jù)規(guī)模時(shí)，都要計(jì)算

上面只是有一個(gè)輸入數(shù)據(jù)，規(guī)模是 n 的時(shí)候，復(fù)雜度與 n 有關(guān)。

如果有兩個(gè)輸入數(shù)據(jù)，規(guī)模分別為 m 和 n 的時(shí)候，那都要計(jì)算上，不能省略，因?yàn)槎际亲兓摹?/p>

也就是 O(m + n)、 O(m * n) 這種。

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

我們明白了什么是 1，什么是 n，什么時(shí)候要同時(shí)計(jì)算 m 和 n，什么是漸進(jìn)復(fù)雜度，為什么常數(shù)可以省略之后，就可以看一些實(shí)際的復(fù)雜度的例子了。

其實(shí)復(fù)雜度也就這么幾種：O(n)、O(n^2)、O(logn)、O(2^n)、O(n!)

O(n)

function func(n) { 
    const a = 1; 
    for(let i = 0; i < n; i ++) { 
        //... 
    } 
} 

這種就是 O(n)，我們上面分析過。常數(shù)復(fù)雜度省略掉。

O(n^2) O(n^3)

function func(n) { 
    for(let i = 0; i < n; i ++) { 
        for(let j = 0; j < n; j ++) { 
            //... 
        } 
    } 
} 

這種就是 O(n^2)，同理，O(n^3)、O(n^4)等也一個(gè)意思，就是嵌套的時(shí)候，復(fù)雜度相乘。

O(logn)

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

這段代碼要計(jì)算多少次，要看 i 乘以幾次 2 才大于 100，也就是 log2n

那同理，也有 log3n，log4n 等復(fù)雜度，當(dāng)漸進(jìn)復(fù)雜度的時(shí)候，常數(shù)是不用計(jì)算的，所以都是 O(logn)

o(2^n) o(3^n)

const fibnacci = function (n) {  
    if (n <= 1) return n;  
    return fibnacci(n - 1) + fibnacci(n - 2); 
}; 

斐波那契數(shù)列我們都知道，可以用上面的遞歸來算。

這樣算的話，n 每加 1，就多遞歸調(diào)用了 2 次 fibnacci 函數(shù)，也就是復(fù)雜度乘以 2 了，所以復(fù)雜度是 O(2^n)。

同理，如果 n 每加一，多遞歸執(zhí)行 3 次，那就是 O(3^n) 的復(fù)雜度。

也就是說，n 每加一，多遞歸 a 次，那復(fù)雜度就是 O(a^n)。

O(n!)

function func(n) {  
    for(let i=0; i<n; i++) {  
        func(n-1);  
    } 
} 

上一條我們知道了，n 每加 1，多遞歸常數(shù)次，是指數(shù)型，那如果如果當(dāng) n 每加 1，多遞歸 n 次，這種就是復(fù)雜度 o(n!) 了。

為什么不是 O(n^n) 呢?因?yàn)?n 是變化的啊，所以是 O(n!)。

這基本是全部的時(shí)間復(fù)雜度情況了。當(dāng)然，這里只是討論了 n 一個(gè)緯度，再多一個(gè)緯度 m 的話，也是一樣。

下面我們來區(qū)分一下這些時(shí)間復(fù)雜度的優(yōu)劣。

時(shí)間復(fù)雜度的優(yōu)劣對(duì)比

我們學(xué)習(xí)了大 O 的漸進(jìn)時(shí)間復(fù)雜度表示法，就是為了估算 n 與具體執(zhí)行時(shí)間的關(guān)系。上面分析出的幾種時(shí)間復(fù)雜度，它們與具體執(zhí)行時(shí)間的關(guān)系是什么樣的呢?可以畫出變化函數(shù)來分析。

可以看到，隨著 n 的增大， O(n!) 和 O(2^n) 是耗時(shí)增加最快的，也就是說，這樣的代碼，n一旦大了，立馬會(huì)卡死，不用跑我們就能分析出來。

那什么樣是的不容易卡死的呢?O(n)、O(nlogn)、o(logn)這種，隨著數(shù)據(jù)規(guī)模的增大，耗時(shí)也不會(huì)增大很多。

所以我們說:

• O(n!)、O(2^n) 的時(shí)間復(fù)雜度都是特別高的，是不好的，是要避免的。
• O(n)、O(nlogn)、O(logn) 的時(shí)間復(fù)雜度是比較低的，是好的，是要盡量采用的。

根據(jù)這個(gè)結(jié)論，我們就可以評(píng)判一些代碼寫法的好壞，也就是算法的優(yōu)劣了。

需要真實(shí)去跑代碼么?不需要。

空間復(fù)雜度

空間復(fù)雜度也就是堆棧內(nèi)存的分配與輸入數(shù)據(jù)規(guī)模 n 的關(guān)系。

這里不包括全局變量，為什么呢?全局變量不會(huì)動(dòng)態(tài)變啊，就相當(dāng)于常數(shù)，可以省略，只分析變化的堆棧內(nèi)存的復(fù)雜度就好了。

空間復(fù)雜度的分析方式和時(shí)間復(fù)雜度是類似的，只是不是把每一條語句作為 1，而是只把會(huì)分配內(nèi)存的語句作為 1 來分析。

比如下面這段代碼的空間復(fù)雜度就是 O(n)。

function func(n) { 
    let arr = []; 
    for (let i = 0; i < n; i++) { 
        arr.push(i); 
    } 
} 

總結(jié)

分析性能一般通過運(yùn)行時(shí)的 Profiler 來收集數(shù)據(jù)，然后分析耗時(shí)和內(nèi)存占用，比如 chrome devtoos 的 performance 和 memory 工具。

但是其實(shí)不用運(yùn)行代碼，我們也可以通過復(fù)雜度來估算出來：

我們把一條語句作為復(fù)雜度是 1，而隨著輸入數(shù)據(jù)規(guī)模 n 變化的為復(fù)雜度 n。

我們估算是為了分析出耗時(shí)/內(nèi)存占用隨著數(shù)據(jù)規(guī)模 n 的一個(gè)變化關(guān)系，所以會(huì)用 O(n) 來表達(dá)這種變化關(guān)系，叫做漸進(jìn)時(shí)間復(fù)雜度。

求漸進(jìn)時(shí)間復(fù)雜度時(shí)，常數(shù)可以省略，因?yàn)樗鼈兪枪潭ú蛔兊?，而我們只需要分析變化的部分?/p>

復(fù)雜度基本就 O(n) O(logn) O(n^2) O(2^n) O(n!) 這幾種。

其中要注意的是 O(2^n) 就是當(dāng) n 每加一，多遞歸 2 次，而如果 n 每加 1，多遞歸 n 次，那么就是 O(n!) 的復(fù)雜度。

O(2^n) 和 O(n!) 的復(fù)雜度都是隨著 n 增加，復(fù)雜度急劇增加的，也就是耗時(shí)/內(nèi)存占用會(huì)急劇增加，這樣的代碼很容易卡死，所以是不好的。

而 O(logn) O(n) 都是隨著 n 增加，復(fù)雜度增加很少的。也就意味了耗時(shí)更少，內(nèi)存占用更少。這樣的算法當(dāng)然也就更好了。

所以我們就是通過復(fù)雜度來評(píng)價(jià)算法好壞的，它就代表了耗時(shí)/內(nèi)存占用，但不是直接表示的，而是抽象的表示。

如果說想得到不同機(jī)器、環(huán)境下的具體耗時(shí)/內(nèi)存占用，那么就用 Profiler 在運(yùn)行時(shí)收集數(shù)據(jù)，然后做分析和可視化，否則，其實(shí)通過復(fù)雜度就能夠抽象的估算出來大概的耗時(shí)和內(nèi)存占用。

性能分析不一定得用 Profiler，復(fù)雜度分析也行，它能評(píng)價(jià)一個(gè)代碼寫法(算法)的好壞，進(jìn)而估算出性能。