[[346356]]

 0. 前言

大家好，我是多選參數(shù)的程序鍋，一個(gè)正在“研究”操作系統(tǒng)(主要是容器這塊)、學(xué)數(shù)據(jù)結(jié)構(gòu)和算法以及 Java 的硬核菜雞。今天這篇主要是講算法的時(shí)間、空間復(fù)雜度，參考來(lái)源主要是王爭(zhēng)老師的專欄《數(shù)據(jù)結(jié)構(gòu)與算法之美》以及程序鍋去年上課時(shí)老師的課件。

另外，程序鍋整了一個(gè)關(guān)于算法的 github 倉(cāng)庫(kù)：https://github.com/DawnGuoDev/algorithm，該倉(cāng)庫(kù)除包含基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)和算法實(shí)現(xiàn)之外，還會(huì)有數(shù)據(jù)結(jié)構(gòu)和算法的知識(shí)內(nèi)容整理、LeetCode 刷題記錄(多種解法、Java 實(shí)現(xiàn)) 、一些優(yōu)質(zhì)書(shū)籍整理。

復(fù)雜度分析是整個(gè)算法學(xué)習(xí)的精髓，只要掌握了它，數(shù)據(jù)結(jié)構(gòu)和算法的內(nèi)容基本上就掌握了一半。”

1. Motivation - 為什么需要復(fù)雜度分析

事后統(tǒng)計(jì)法(也就是把代碼運(yùn)行一遍，通過(guò)統(tǒng)計(jì)、監(jiān)控得到運(yùn)行的時(shí)間和占用的內(nèi)存大小)的測(cè)試結(jié)果非常依賴測(cè)試環(huán)境以及受數(shù)據(jù)規(guī)模的影響程度非常大。但是實(shí)際上更需要一個(gè)不用具體的測(cè)試數(shù)據(jù)就可以估計(jì)出算法的執(zhí)行效率的方法。

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

算法的執(zhí)行效率簡(jiǎn)單來(lái)說(shuō)就是算法的執(zhí)行時(shí)間。比如下面這段代碼的執(zhí)行時(shí)間，假設(shè)每行代碼執(zhí)行的時(shí)間是一樣的，都為 unit_time。在這個(gè)假設(shè)的基礎(chǔ)之上，這段代碼的總執(zhí)行時(shí)間為 (2n + 2)* unit_time。

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

通過(guò)這個(gè)例子，可以看出總執(zhí)行時(shí)間 T(n) 是與每行代碼的執(zhí)行次數(shù)成正比，即可以滿足這個(gè)公式 T(n) = O(f(n))，其中 n 是數(shù)據(jù)規(guī)模的大小，f(n) 表示每行代碼執(zhí)行的總次，O() 表示一個(gè)函數(shù)，即 T(n) 與 f(n) 成正比。在這個(gè)例子中 T(n) = O(2n+2)，這種方式就被稱為大 O 復(fù)雜度表示法。但是實(shí)際上，大 O 時(shí)間復(fù)雜度并不具體表示代碼執(zhí)行真正的執(zhí)行時(shí)間，而是表示代碼執(zhí)行時(shí)間隨數(shù)據(jù)規(guī)模增長(zhǎng)的變化趨勢(shì)，也叫做漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。那么，在 2n+2 這個(gè)式子中，系數(shù) 2 和 常數(shù) 2 并不左右增長(zhǎng)趨勢(shì)，比如它是線性，并不是會(huì)因?yàn)橄禂?shù) 2 或者常數(shù) 2 改變它線性增長(zhǎng)的趨勢(shì)，因此又可以寫(xiě)成T(n)=O(n)。又比如 T(n) = O(n^2)，那么表示代碼執(zhí)行時(shí)間隨數(shù)據(jù)規(guī)模 n 增長(zhǎng)的變化趨勢(shì)是 n 平方。下面這張圖是不同時(shí)間復(fù)雜度，隨數(shù)據(jù)規(guī)模增長(zhǎng)的執(zhí)行時(shí)間變化

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

如何對(duì)一段代碼的時(shí)間復(fù)雜度進(jìn)行分析呢?可以采用以下幾種方法

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

因?yàn)榇?O 復(fù)雜度表示法只是表示一種趨勢(shì)，所以可以忽略掉公式中的常數(shù)項(xiàng)、低階、系數(shù)等，只記錄一個(gè)最大的量級(jí)就可以了。因此在分析一個(gè)算法、一段代碼的復(fù)雜度的時(shí)候，只需要關(guān)注循環(huán)次數(shù)最多的那一段代碼就行了。比如下面這段代碼，時(shí)間復(fù)雜度是 O(n)

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

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

這個(gè)主要是省略掉大 O 復(fù)雜度中的低階項(xiàng)。個(gè)人感覺(jué)這個(gè)方法跟上面的方法有些重合。比如下面這段代碼中，可以按照循環(huán)分為三個(gè)段，第一個(gè)段中有個(gè)循環(huán)，但是循環(huán)次數(shù)是個(gè)常數(shù)項(xiàng)，對(duì)增長(zhǎng)趨勢(shì)無(wú)任何影響，因此時(shí)間復(fù)雜度是 O(1)，第二段代碼的時(shí)間復(fù)雜度是 O(n)，第三個(gè)段代碼的時(shí)間復(fù)雜度是 O(n^2)。這三個(gè)段中量級(jí)最大的那個(gè)時(shí)間復(fù)雜度也就是整段代碼的時(shí)間復(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; 
} 

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

比如下面這段代碼中，f() 是一個(gè)循環(huán)操作，整個(gè)復(fù)雜度是 O(n)，而 cal() 中的循環(huán)相當(dāng)于外層，調(diào)用了 f()，假如把 f() 當(dāng)成一個(gè)簡(jiǎn)單的操作的話，那么時(shí)間復(fù)雜度是 O(n)，算上 f() 真實(shí)的復(fù)雜度之后，整個(gè) cal() 的時(shí)間復(fù)雜度是 O(n)*O(n)=O(n*n) = O(n^2)。

int cal(int n) { 
    int ret = 0;  
    int i = 1; 
    for (; i < n; ++i) { 
        ret = ret + f(i); 
    }  
}  
 
int f(int n) { 
    int sum = 0; 
    int i = 1; 
    for (; i < n; ++i) { 
        sum = sum + i; 
    }  
    return sum; 
} 

3.1. 常見(jiàn)時(shí)間復(fù)雜度

下面針對(duì)上述的若干種時(shí)間復(fù)雜度進(jìn)行闡述：

1.O(1)

O(1)是常量級(jí)時(shí)間復(fù)雜度的一種表示，只要代碼的時(shí)間不隨 n 的增大而增大，那么它的時(shí)間復(fù)雜也是 O(1)。一般情況下，只要算法中不存在循環(huán)語(yǔ)句、遞歸語(yǔ)句，即使有成千上萬(wàn)行的代碼，其時(shí)間復(fù)雜度也是 O(1)。

2.O(logn)、O(nlogn)

對(duì)數(shù)時(shí)間復(fù)雜度往往比較難分析，比如下面這段代碼中

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

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

O(nlogn) 的時(shí)間復(fù)雜度就相當(dāng)于上面說(shuō)到的“乘法法則”：一段代碼的時(shí)間復(fù)雜度為O(logn) ，這段代碼循環(huán) n 次，時(shí)間復(fù)雜度就是 O(nlogn) 了。

3.O(m+n)、O(m*n)

這種情況下，代碼的復(fù)雜度是由兩個(gè)數(shù)據(jù)規(guī)模決定的。如下代碼所示：

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; 
} 

從這段代碼中可以看出m 和 n 是兩個(gè)數(shù)據(jù)規(guī)模，無(wú)法評(píng)估 m 和 n 的量級(jí)大小。因此，不能省略其中任何一個(gè)，所以就是 O(m+n) 了。

4.O(2^n)、O(n!)

在上述表格中列出的復(fù)雜度量級(jí)，可以粗略的分為兩類：多項(xiàng)式量級(jí)和非多項(xiàng)式量級(jí)。其中非多項(xiàng)式量級(jí)只有這兩個(gè)。非多項(xiàng)式量級(jí)的算法問(wèn)題也叫做 NP(Non-Deterministic Ploynomial，非確定多項(xiàng)式)問(wèn)題。當(dāng) n 越來(lái)越大時(shí)，非多項(xiàng)式量級(jí)算法的執(zhí)行時(shí)間會(huì)急劇增加，求解問(wèn)題的執(zhí)行時(shí)間也會(huì)無(wú)限增長(zhǎng)，所以是種很低效的算法。

3.2. 最好、最壞情況時(shí)間復(fù)雜度

比如下面這段代碼中，是在數(shù)組中查找一個(gè)數(shù)據(jù)，但是并不是把整個(gè)數(shù)組都遍歷一遍，因?yàn)橛锌赡苤型菊业搅司涂梢蕴崆巴顺鲅h(huán)。那么，最好的情況是如果數(shù)組中第一個(gè)元素正好是要查找的變量 x ，時(shí)間復(fù)雜度就是 O(1)。最壞的情況是遍歷了整個(gè)數(shù)組都沒(méi)有找到想要的 x，那么時(shí)間復(fù)雜就成了 O(n)。因此 O(1) 就是這段代碼的最好情況時(shí)間復(fù)雜度，也就是在最好的情況下，執(zhí)行這段代碼的時(shí)間復(fù)雜度。O(n) 就是這段代碼的最壞情況時(shí)間復(fù)雜度。

// n表示數(shù)組array的長(zhǎng)度 
int find(int[] array, int n, int x) { 
    int i = 0; 
    int pos = -1; 
    for (; i < n; ++i) { 
        if (array[i] == x) { 
            pos = i; 
            break; 
        } 
    } 
    return pos; 
} 

3.3. 平均情況時(shí)間復(fù)雜度(加權(quán)平均時(shí)間復(fù)雜度或者期望時(shí)間復(fù)雜度)

最好和最壞情況時(shí)間復(fù)雜度都是極端情況發(fā)生的時(shí)間復(fù)雜度，并不常見(jiàn)。因此可以使用平均情況時(shí)間復(fù)雜度來(lái)表示。比如上面這段代碼中查找 x 在數(shù)組中的位置有兩種情況，一種是在數(shù)組中，另一種是不在數(shù)組中。在數(shù)組中又可以在數(shù)組中的 0~n-1 位置。假設(shè)在數(shù)組中和不在數(shù)組中的概率分別為 1/2，在數(shù)組中的 0~n-1 的位置概率都一樣，為 1/(2 *n)。因此，上述這段的平均情況時(shí)間復(fù)雜度(或者叫加權(quán)平均時(shí)間復(fù)雜度、期望時(shí)間復(fù)雜度)為

假如使用如下公式計(jì)算復(fù)雜度的話，那么就相當(dāng)于每種情況的發(fā)生概率都是 1/(n+1) 了，沒(méi)有考慮每種的情況的不同概率，存在一定不準(zhǔn)確性。

3.4. 均攤時(shí)間復(fù)雜度

均攤時(shí)間復(fù)雜度采用的是攤還分析法(平攤分析法)。就是把耗時(shí)多的操作，平攤到其他那些時(shí)間復(fù)雜度比較低的操作上。比如下面這段代碼

// array表示一個(gè)長(zhǎng)度為n的數(shù)組 
// 代碼中的array.length就等于n 
int[] array = new int[n]; 
int count = 0; 
 
void insert(int val) { 
    if (count == array.length) { 
        int sum = 0; 
        for (int i = 0; i < array.length; ++i) { 
            sum = sum + array[i]; 
        } 
        array[0] = sum; 
        count = 1; 
    } 
 
    array[count] = val; 
    ++count; 
} 

這段代碼想要實(shí)現(xiàn)的就是往一個(gè)數(shù)組中插入數(shù)據(jù)，如果數(shù)組滿了的話，那么就求和之后的 sum 放到數(shù)組的第一個(gè)位置，之后繼續(xù)將數(shù)據(jù)插入到數(shù)組中。通過(guò)分析可以發(fā)現(xiàn)，這段代碼的最好情況時(shí)間復(fù)雜度是 O(1)，最壞情況時(shí)間復(fù)雜度是 O(n)，平均時(shí)間復(fù)雜度是 O(1)。

那么這段代碼中，在大部分情況下，時(shí)間復(fù)雜度是 O(1)，只有個(gè)別情況下，復(fù)雜度才是 O(n)。并且，O(1) 和 O(n) 出現(xiàn)的比較規(guī)律，一般一個(gè) O(n) 執(zhí)行之后，會(huì)出現(xiàn) n-1 個(gè) O(1) 的執(zhí)行。針對(duì)這種情況，可以使用攤還分析法，就是把 O(n) 這個(gè)耗時(shí)多的時(shí)間復(fù)雜度均攤到接下來(lái)的 n-1 個(gè) O(1) 的執(zhí)行上，均攤下來(lái)的時(shí)間復(fù)雜度為 O(1)，這個(gè)時(shí)間復(fù)雜度就是均攤時(shí)間復(fù)雜度。

那么均攤時(shí)間復(fù)雜度不怎么常見(jiàn)，常見(jiàn)的場(chǎng)景是：對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行一組連續(xù)操作，大部分情況下時(shí)間復(fù)雜度都很低，只有個(gè)別情況下時(shí)間復(fù)雜度比較高。而且這些操作之間存在前后連貫的時(shí)序關(guān)系，比如上面提到的先是一系列 O(1) 的時(shí)間復(fù)雜度操作，接下來(lái)是 O(n) 的時(shí)間復(fù)雜度操作。這個(gè)時(shí)候就可以采用攤還分析法將較高時(shí)間復(fù)雜度的那次操作的耗時(shí)平攤到其他時(shí)間復(fù)雜度比較低的操作上。

一般均攤時(shí)間復(fù)雜度等于最好情況時(shí)間復(fù)雜度。那么如何區(qū)別平均時(shí)間復(fù)雜度和均攤時(shí)間復(fù)雜度呢?我覺(jué)得看你使用哪種方法，假如使用攤還分析法算出來(lái)的時(shí)間復(fù)雜度就是均攤時(shí)間復(fù)雜度，使用加權(quán)方式、或者期望值計(jì)算方式算出來(lái)的時(shí)間復(fù)雜度就是平均時(shí)間復(fù)雜度。

4. 空間復(fù)雜度分析

空間復(fù)雜度分析方法很簡(jiǎn)單。時(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)系。

比如下面這段代碼中，首先 int i= 0; 申請(qǐng)一個(gè)空間存儲(chǔ)變量，是常量可以忽略，int[] a = new int[n]; 申請(qǐng)了一個(gè)大小為 n 的 int 類型數(shù)組，剩下的代碼都沒(méi)有占用更多的空間，因此空間復(fù)雜度是 O(n)

void print(int n) { 
    int i = 0; 
    int[] a = new int[n]; 
    for (i; i <n; ++i) { 
        a[i] = i * i; 
    } 
 
    for (i = n-1; i >= 0; --i) { 
        print out a[i] 
    } 
} 

對(duì)于空間復(fù)雜度分析，其實(shí)比較簡(jiǎn)單，一般看變量聲明時(shí)分配的空間大小即可。

4.1. 常用時(shí)間復(fù)雜度

常用的空間復(fù)雜度就上面 3 種，O(nlogn)、O(logn)這樣的對(duì)數(shù)階復(fù)雜度一般都用不到。

5. 總結(jié)

回顧一下復(fù)雜度分析，總的來(lái)說(shuō)時(shí)間復(fù)雜度的 motivation 是我們想要一個(gè)不用具體數(shù)據(jù)就可以估算出算法的執(zhí)行效率的方法。而時(shí)間復(fù)雜度采用的是大 O 表示法，大 O 表示法其實(shí)描述的是一個(gè)增長(zhǎng)趨勢(shì)。比如 n^2 中，當(dāng) n 的值越來(lái)越大時(shí)候，O(n^2) 這個(gè)算法的執(zhí)行時(shí)間是成平方增長(zhǎng)的，而 O(n) 這個(gè)算法的執(zhí)行時(shí)間是成直線型增長(zhǎng)的，因此 O(n^2) 的時(shí)間復(fù)雜度是更高(見(jiàn)第一張圖)。之后是幾種常用的時(shí)間復(fù)雜度，平均時(shí)間復(fù)雜度、最好最壞時(shí)間復(fù)雜度，均攤時(shí)間復(fù)雜度(均攤這種思想在操作系統(tǒng)中有一定的體現(xiàn)：RR 調(diào)度算法中，在時(shí)間片大小選擇上，有著類似的處理方式，因?yàn)?RR 是一個(gè)搶占式調(diào)度算法，當(dāng)發(fā)生調(diào)度之后會(huì)發(fā)生進(jìn)程的上下文切換，而進(jìn)程的上下文切換是需要額外的時(shí)間成本，而這個(gè)時(shí)間成本會(huì)均攤到時(shí)間片上，當(dāng)時(shí)間片很大時(shí)，顯然均攤的效果不錯(cuò)，因此這個(gè)額外的時(shí)間成本影響會(huì)很小)

為什么說(shuō)掌握時(shí)間復(fù)雜度是掌握了根本大法?去年上課的時(shí)候，記憶比較深刻的是老師好像在講一個(gè)比較難的算法問(wèn)題，然后從最簡(jiǎn)單、復(fù)雜度最高的解法開(kāi)始講起，然后跟帶著我們一步一步分析每一塊代碼的時(shí)間復(fù)雜度，然后說(shuō)這塊的代碼的時(shí)間復(fù)雜度是 O(n^2)，我們能不能想辦法把它給降下來(lái)的呢?然后就在那思考了怎么降了，一句一句代碼看過(guò)去，畫(huà)圖等等，最終將時(shí)間復(fù)雜度降下來(lái)了。因此個(gè)人覺(jué)得掌握時(shí)間復(fù)雜度分析之后，掌握的是算法的分析方法，你可以分析出每段代碼的復(fù)雜度，然后通過(guò)思考最終把相應(yīng)代碼的時(shí)間復(fù)雜度降下來(lái)。假如你復(fù)雜度分析掌握不熟，那么怎么降都不知道，那么算法的優(yōu)化也就沒(méi)了。

本文轉(zhuǎn)載自微信公眾號(hào)「多選參數(shù)」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系多選參數(shù)公眾號(hào)。