[[354643]]

在開(kāi)發(fā)的時(shí)候，我們?nèi)绾卧u(píng)估一個(gè)算法的好壞，如何描述一個(gè)算法運(yùn)行效率的高低呢?通俗一點(diǎn)的表達(dá)方法就是程序執(zhí)行快或慢，但是這只是一種較為寬泛的描述，我們?nèi)绾沃庇^(guān)科學(xué)的用的描述它呢?

有同學(xué)可能會(huì)說(shuō)，用其運(yùn)行時(shí)間不就可以很好很直觀(guān)的描述它了。不過(guò)，不同的語(yǔ)言，不同的編譯器，不同的CPU來(lái)說(shuō)，對(duì)程序的處理的時(shí)間是不同的，我們無(wú)法單單用運(yùn)行時(shí)間來(lái)描述某個(gè)算法執(zhí)行效率。另外，當(dāng)需要處理的數(shù)據(jù)增長(zhǎng)時(shí)，算法的基本操作要重復(fù)執(zhí)行的次數(shù)也會(huì)增長(zhǎng)，對(duì)于不同的算法的增長(zhǎng)的速度也不一樣。

數(shù)學(xué)果然是個(gè)不錯(cuò)的工具，為了描述算法的運(yùn)行時(shí)間的增長(zhǎng)情況，我們可以用不同數(shù)學(xué)公式來(lái)分析。在計(jì)算機(jī)科學(xué)上，我們是有專(zhuān)門(mén)的術(shù)語(yǔ)來(lái)表征算法的效率，就是今天要和大家一起學(xué)習(xí)的大O表示法。大O并不是表示算法運(yùn)行需要多長(zhǎng)時(shí)間，它表示的是算法運(yùn)行時(shí)間的增速，即算法的運(yùn)行時(shí)間以不同的速度增加，也叫漸進(jìn)時(shí)間復(fù)雜度。

我們可以用下面的表達(dá)式來(lái)表示：

通常主要有以下幾種表達(dá)式來(lái)描述時(shí)間復(fù)雜度：

• O(1)：常量時(shí)間
• O(n)：線(xiàn)性時(shí)間
• O(log n)：對(duì)數(shù)時(shí)間
• O(n^2)：二次方時(shí)間
• O(2^n)：指數(shù)時(shí)間
• O(n!)：階乘時(shí)間

每種時(shí)間復(fù)雜度有所不同，下面我們一起來(lái)詳細(xì)了解這幾種時(shí)間復(fù)雜度。

大O復(fù)雜度

O(1)

O(1)表示常量時(shí)間復(fù)雜度，當(dāng)給定大小為n的輸入，無(wú)論n為何值，最后算法執(zhí)行的時(shí)間是個(gè)常量。舉個(gè)例子：

int func(int n) 
{ 
    n++; 
    return n*2; 
} 

上面的程序中，無(wú)論輸入n的值如何變化，程序執(zhí)行時(shí)間始終是個(gè)常量。我們簡(jiǎn)化處理一下，假如函數(shù)中每行語(yǔ)句的執(zhí)行時(shí)間是1，則執(zhí)行時(shí)間的數(shù)學(xué)表達(dá)式：

無(wú)論n為多大，最后的執(zhí)行時(shí)間都是2這個(gè)固定值。雖然是運(yùn)行時(shí)間為2，但是這里我們也用O(1)來(lái)表示，這里的1代表是一個(gè)常數(shù)。

O(n)

O(n)表示線(xiàn)性時(shí)間復(fù)雜度，算法的執(zhí)行時(shí)間隨著輸入n的大小成線(xiàn)性變化。

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

上面的這個(gè)程序中，函數(shù)的執(zhí)行時(shí)間隨著n的變化成線(xiàn)性的關(guān)系。

對(duì)于這種可以用線(xiàn)性表達(dá)式表示的情況，我們用O(n)來(lái)表示。

為什么可以省略掉表達(dá)式中的其他系數(shù)呢?主要是當(dāng)n趨近于無(wú)窮大時(shí)，系數(shù)相對(duì)于無(wú)窮大的n來(lái)說(shuō)可以忽略不計(jì)。

O(n^2 )

O(n^2)表示二次方時(shí)間復(fù)雜度，一個(gè)算法的時(shí)間將會(huì)隨著輸入數(shù)據(jù)n的增長(zhǎng)而呈現(xiàn)出二次關(guān)系增加。

int func(int n) 
{ 
    int sum = 0; 
    for(int i=0; i<n; i++) 
    { 
        for(int j=0; j<n; j++) 
        { 
            sum = sum + i + j; 
        } 
    } 
 
    return sum; 
} 

上面的程序中，是個(gè)兩層循環(huán)的程序，函數(shù)的執(zhí)行時(shí)間和n是二次方的關(guān)系：

對(duì)于這種類(lèi)型的程序，我們可以用O(n^2)表示。不過(guò)，循環(huán)嵌套除了這種兩層循環(huán)之外，還會(huì)有三層、四層...n層循環(huán)，對(duì)應(yīng)的其復(fù)雜度就是O(n^3) 、O(n^4)...O(n^n)。

O(2^n)

O(2^n)表示指數(shù)復(fù)雜度，隨著n的增加，算法的執(zhí)行時(shí)間成倍增加，它是一種爆炸式增長(zhǎng)的情況。

int func(int n) 
{ 
    if(n==0) return 1; 
 
    return func(n) + func(n-1) 
} 

上面的代碼中，有兩次遞歸調(diào)用，函數(shù)的執(zhí)行時(shí)間就會(huì)和輸入n成指數(shù)的關(guān)系。

因此，這里我們可以用O(2^n)表示。

O(log n)

O(log n)表示對(duì)數(shù)時(shí)間復(fù)雜度，算法執(zhí)行時(shí)間和n是一種對(duì)數(shù)關(guān)系。這種類(lèi)型的算法會(huì)在執(zhí)行的過(guò)程中，隨著程序的執(zhí)行其完成某個(gè)功能的操作步驟越來(lái)越少。其中，我們所熟知的二分查找法就是一個(gè)很好的例子。比如，下面這個(gè)代碼在一個(gè)有序列表中查找某個(gè)值的位置，我們通過(guò)二分法進(jìn)行查找。

int func(int a[], int size, int num) 
{ 
    int left = 0; 
    int right = size-1; 
 
    while(left <= right) 
    { 
        int mid = (left + right)/2; 
 
        if(a[mid] > num) 
        { 
            right = mid - 1; 
        } 
        else if (a[mid] < num) 
        { 
            left = mid + 1; 
        } 
        else 
        { 
            return num; 
        } 
    } 
 
    return -1; 
} 

在最糟糕的情況下，我們通過(guò)二分法拆分x次后，最后一個(gè)元素就是我們要找的元素。我們可以得到下面的等式：

函數(shù)運(yùn)行時(shí)間可以表示為：

因此，這里我們可以用O(log n)表示。

O(n!)

對(duì)于階乘關(guān)系的復(fù)雜度，最典型的例子就是旅行商問(wèn)題。

假設(shè)有一個(gè)旅行商人要拜訪(fǎng)n+1個(gè)城市，他必須選擇所要走的路徑，路徑的限制是每個(gè)城市只能拜訪(fǎng)一次，而且最后要回到原來(lái)出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑長(zhǎng)度為所有路徑之中的最小值。

這個(gè)問(wèn)題最簡(jiǎn)單的方法是通過(guò)窮舉法列出所有的排列組合。如果有n+1個(gè)城市，根據(jù)我們數(shù)學(xué)中學(xué)過(guò)的排列組合計(jì)算方法，可以算出所有組合數(shù)為n!，所以這種窮舉法對(duì)應(yīng)的時(shí)間復(fù)雜度也就是O(n!)了。

本文轉(zhuǎn)載自微信公眾號(hào)「Will的大食堂」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系Will的大食堂公眾號(hào)。