算法時(shí)間復(fù)雜度分析：大O表示法

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

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

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

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

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

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

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

大O復(fù)雜度

O(1)

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

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

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

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

O(n)

O(n)表示線性時(shí)間復(fù)雜度，算法的執(zhí)行時(shí)間隨著輸入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的變化成線性的關(guān)系。

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

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

O(n^2 )

O(n^2)表示二次方時(shí)間復(fù)雜度，一個(gè)算法的時(shí)間將會(huì)隨著輸入數(shù)據(jù)n的增長而呈現(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)系：

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

O(2^n)

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

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

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

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

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

O(n!)

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

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

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