摘要：原文地址數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記時(shí)間復(fù)雜度時(shí)間復(fù)雜度定義在進(jìn)行算法分析時(shí)，語句總的執(zhí)行次數(shù)是關(guān)于問題規(guī)模的函數(shù)，進(jìn)而分析隨的變化情況并確定的數(shù)量級(jí)。同理，對(duì)于單純分支結(jié)構(gòu)不包含在循環(huán)中的或語句而言，執(zhí)行的次數(shù)都是恒定的，其時(shí)間復(fù)雜度也是。

原文地址：數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記-時(shí)間復(fù)雜度

在進(jìn)行算法分析時(shí)，語句總的執(zhí)行次數(shù)T(n)是關(guān)于問題規(guī)模n的函數(shù)，進(jìn)而分析T(n)隨n的變化情況并確定T(n)的數(shù)量級(jí)。算法的時(shí)間復(fù)雜度，也就是算法的時(shí)間量度，記作：T(n) = O(f(n))。它表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長率和f(n)的增長率相同，稱作算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱為時(shí)間復(fù)雜度。其中f(n)是問題規(guī)模n的某個(gè)函數(shù)。

這樣用大寫O()來體現(xiàn)算法的時(shí)間復(fù)雜度的記法，我們稱之為大O記法。

如何分析一個(gè)算法的時(shí)間復(fù)雜度呢？即如何推導(dǎo)大O階呢？我們可以參考下面的推導(dǎo)方法。

推導(dǎo)大O階：
1. 用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)。
2. 在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)。
3. 如果最高階項(xiàng)存在且不是1，則去除與這個(gè)項(xiàng)相乘的常數(shù)。
得到的結(jié)果就是大O階。

下面讓我們根據(jù)這個(gè)推導(dǎo)方法來看幾個(gè)例子。

int sum = 0,n = 100;  /* 執(zhí)行一次 */
sum = (1 + n) * n/2;  /* 執(zhí)行一次 */
System.out.println(sum);  /* 執(zhí)行一次 */

這段程序的執(zhí)行次數(shù)是f(3)。我們使用大O階的方法推導(dǎo)一下：

將常數(shù)項(xiàng)3改為1。

保留最高階項(xiàng)。

沒有最高階項(xiàng)，所以這段程序的時(shí)間復(fù)雜度為O(1).

可以試想一下，如果這段代碼里的

sum = (1 + n) * n/2;  /* 執(zhí)行一次 */

一共有10句，那么時(shí)間復(fù)雜度是多少呢？

事實(shí)上，無論有多少句該代碼，都不過是3次和多次的執(zhí)行差異。像這種執(zhí)行時(shí)間恒定的算法，我們稱之為具有O(1)的時(shí)間復(fù)雜度，又叫常數(shù)階。

注意：無論這個(gè)常數(shù)是多少，我們都記作O(1)。

同理，對(duì)于單純分支結(jié)構(gòu)（不包含在循環(huán)中的if或switch語句）而言，執(zhí)行的次數(shù)都是恒定的，其時(shí)間復(fù)雜度也是O(1)。

線性階的循環(huán)結(jié)構(gòu)會(huì)復(fù)雜一些。要確定某個(gè)算法的階次，我們常常需要確定某個(gè)特定語句或某個(gè)語句集的運(yùn)行次數(shù)。因此，我們要分析算法的復(fù)雜度，關(guān)鍵就是要分析循環(huán)結(jié)構(gòu)的運(yùn)行情況。

下面這段代碼，它的循環(huán)時(shí)間復(fù)雜度為O(n)，因?yàn)檠h(huán)中的代碼須要執(zhí)行n次。

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

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

由于每次count乘以2之后，就離n更近了一些。也就是是，有多少個(gè)2相乘后大于n，則會(huì)退出循環(huán)。由2^x=n得到x=log2n(以2為底n的對(duì)數(shù))。所以這個(gè)循環(huán)的時(shí)間復(fù)雜度為O(logn)。

下面例子是一個(gè)循環(huán)嵌套，它的內(nèi)循環(huán)時(shí)間復(fù)雜度為O(n)。

int i,j;
for(i = 0; i < n; i++){
    for(j = 0; j < n; j++){
    
    }
}

對(duì)于外循環(huán)不過是這個(gè)時(shí)間復(fù)雜度為O(n)的語句循環(huán)了n次，所以這段代碼的時(shí)間復(fù)雜度為O(n^2)。

如果外循環(huán)的次數(shù)改為了m，那么時(shí)間復(fù)雜度就變?yōu)榱薕(m*n)。

所以我們可以總結(jié)出來：循環(huán)的時(shí)間復(fù)雜度等于循環(huán)體的復(fù)雜度乘以循環(huán)運(yùn)行的次數(shù)。

那么，下面這段代碼的時(shí)間復(fù)雜度是多少呢？

int i,j;
for(i = 0; i < n; i++){
    for(j = i; j < n; j++){
    
    }
}

我們可以推導(dǎo)一下當(dāng)i = 0 時(shí)，內(nèi)循環(huán)執(zhí)行了n次；當(dāng)i = 1時(shí)，執(zhí)行了n - 1次，……當(dāng) i = n-1時(shí)，執(zhí)行了1次。所以總的執(zhí)行次數(shù)為：

n + (n-1) + (n-2) + …… + 1 = n(n+1)/2 = n^2/2 + n/2

用推導(dǎo)大O階的方法

由于沒有加法常數(shù)，可以不考慮

只保留最高階，也就是保留n^2/2

去除常數(shù)的相乘項(xiàng)，也就是去除1/2

最終，這段代碼的時(shí)間復(fù)雜度就是O(n^2)。

該表列舉了一些常見的時(shí)間復(fù)雜度

常用的時(shí)間復(fù)雜度從小到大依次是：

O(1)