在數(shù)據(jù)結(jié)構(gòu)與算法的學(xué)習(xí)過程中，如果只學(xué)會了其特點，用法，而并沒有掌握算法復(fù)雜度的分析，那就相當(dāng)于只學(xué)會了皮毛，而沒有掌握其靈魂。

由于算法復(fù)雜度的分析較為重要，該部分會分為兩篇文章：今天會介紹怎么分析算法復(fù)雜度，以及常見的復(fù)雜度分析。

首先會教大家怎么去分析算法復(fù)雜度，算法復(fù)雜度主要有兩類：

• 時間復(fù)雜度

• 空間復(fù)雜度

算符復(fù)雜度的表示一般采用大O復(fù)雜度表示法。

時間復(fù)雜度分析

時間復(fù)雜度的全稱是監(jiān)禁時間復(fù)雜度，表示算法的執(zhí)行時間與數(shù)據(jù)規(guī)模之間的增長關(guān)系。

首先，看下面這函數(shù)，假設(shè)每行代碼的運行時間為t，那么這段代碼總的運行時間為多少呢？

int Test(int n) { int i = 1; int k = 1; int j = 0; for(i = 0; i <= n; ++i) {
 k = 1; for(; k <= n; ++k) {
 j = j + i * k;
 }
 }
}

• 第2、3、4行代碼的運行時間分別為1t

• 第5、6行代碼的運行時間分別為n * t

• 第7、8行代碼的運行時間分別為n * n

• 這段代碼總的運行時間為

由上述代碼可知，一段代碼的運行時間T(n)與每行代碼的執(zhí)行次數(shù)n成正比，則T(n) = O(f(n))。

將上述代碼的運行時間代入公式得：

這便是大O時間復(fù)雜度表示法。

該表示法并非表示代碼的運行時間，而是將代碼運行時間隨數(shù)據(jù)規(guī)模增長的變化趨勢表現(xiàn)出來。

由于公式中的低階、常量、系數(shù)并不會左右代碼運行時間的增長趨勢，因此可以將它們?nèi)亢雎浴?

所以，上述公式又可以表示為：

加法法則

說明：程序的總復(fù)雜度等于量級最大的那段代碼的復(fù)雜度

公式：

乘法法則

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

公式：

常見時間復(fù)雜度分析

• 多項式量級

常量階 O(1)
對數(shù)階 O(logn)
線性階 O(n)
線性對數(shù)階 O(nlogn)
平方階 O(n^2)
K方階 O(n^k)

• 非多項式量級

指數(shù)階 O(2^n)
階乘階 O(n!)

• 非多項式量級的算法隨著數(shù)據(jù)規(guī)模n的增大，其代碼執(zhí)行時間會急劇增加。

O(1)

O(1)只是表示常量級時間復(fù)雜度，并不代表代只執(zhí)行了一行代碼。

例如下方代碼的時間復(fù)雜度為O(1)，而并不是O(2)

int i = 0; int j = 1;

對數(shù)階

• O(logN)

• O(NlogN)

示例：

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

上述代碼，當(dāng)i小于等于n時，每循環(huán)一次代碼，變量i的值就會乘以2。因此，變量i的取值為一個等比數(shù)列：

k值即為代碼的循環(huán)次數(shù)，因此，根據(jù)公式

求解出

所以，這段代碼的時間復(fù)雜度為

將上面的代碼進行稍微的修改：

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

根據(jù)之前推論，這段代碼的的時間復(fù)雜度為

但是?。?！這兩段代碼的時間復(fù)雜度都為

下面我們以為例，進行說明。

由于對數(shù)之間是可以進行互相轉(zhuǎn)換的

因此又可以轉(zhuǎn)換為

所以：

在算法復(fù)雜度分析時，可以忽略常量帶來的影響。

所以，

因此，在對數(shù)階時間復(fù)雜度表示中，可以忽略其底數(shù)

將它們統(tǒng)一表示為

O(NlogN)則代表將時間復(fù)雜度為O(logN)的代碼又運行了N遍。

空間雜度分析

空間復(fù)雜度全稱為漸進空間復(fù)雜度，表示算法的存儲空間與數(shù)據(jù)規(guī)模之間的增長關(guān)系。

每段功能完全的代碼在運行過程中都會占用一些存儲空間：

• 代碼本身占用的空間

• 程序中輸入與輸出的數(shù)據(jù)所占用的空間

• 程序在運行中動態(tài)申請的空間

一般程序中動態(tài)申請的空間，對空間復(fù)雜度的影響最大。

int n; scanf("%d", &n); int a[10];

上述代碼在運行時所申請的空間并不會隨著n的增大而增大。
因此該段代碼的空間復(fù)雜度為O(1)

將上述代碼稍作修改

int n; scanf("%d", &n); int a[n];

則該段代碼的空間復(fù)雜度與n有關(guān)，記為O(n)

一般常見的空間復(fù)雜度為O(1)、O(n)、O(n )。