算法時(shí)間復(fù)雜度求解法【詳細(xì)過程說明】
算法的時(shí)間復(fù)雜度，是剛開始接觸算法和數(shù)據(jù)結(jié)構(gòu)時(shí)的概念，在真正使用的時(shí)候有時(shí)候常常忘記它的推導(dǎo)公式。最近準(zhǔn)備校招，把二叉樹、排序、查找等這些經(jīng)典的算法復(fù)習(xí)了一遍，這次把這些都整理成博客以便以后查看，復(fù)習(xí)計(jì)劃接近尾聲，這兩天老是不在狀態(tài)，學(xué)習(xí)圖的時(shí)候有點(diǎn)暈乎乎，今天反過頭來把時(shí)間復(fù)雜度的求解法整理一下，還是頗有收獲，以前很多地方自己存在著理解誤差。希望對(duì)大家也有所幫助，有不對(duì)的地方還請(qǐng)多指教。
在進(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)的增長率相同，稱作算法的漸進(jìn)算法時(shí)間復(fù)雜度，簡稱為時(shí)間復(fù)雜度。其中f(n)是問題規(guī)模n的某個(gè)函數(shù)。
一般用大寫O()來表示算法的時(shí)間復(fù)雜度寫法，通常叫做大O記法。
一般情況下，隨著n的增大，T(n)增長最慢的算法為最優(yōu)算法。
O(1)：常數(shù)階
O(n)：線性階
O(n2)：平方階
大O推導(dǎo)法：
用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)
在修改后的運(yùn)行函數(shù)中，只保留最高階項(xiàng)
如果最高階項(xiàng)存在且不是1，則去除與這個(gè)項(xiàng)相乘的常數(shù)
常數(shù)階：
int sum = 0 ; n = 100; /*執(zhí)行一次*/
sum = (1+n)*n/2; /*執(zhí)行一次*/
printf("%d",sum); /*執(zhí)行一次*/
這個(gè)算法的運(yùn)行次數(shù)f(n) = 3,根據(jù)推導(dǎo)大O階的方法，第一步是將3改為1，在保留最高階項(xiàng)是，它沒有最高階項(xiàng)，因此這個(gè)算法的時(shí)間復(fù)雜度為O(1);
對(duì)于分支結(jié)構(gòu)而言，無論真假執(zhí)行的次數(shù)都是恒定不變的，不會(huì)隨著n的變大而發(fā)生變化，所以單純的分支結(jié)構(gòu)（不在循環(huán)結(jié)構(gòu)中），其時(shí)間復(fù)雜度也是O(1)。
線性階：
線性階的循環(huán)結(jié)構(gòu)會(huì)復(fù)雜一些，要確定某個(gè)算法的階次，需要確定特定語句或某個(gè)語句集運(yùn)行的次數(shù)。因此要分析算法的復(fù)雜度，關(guān)鍵是要分析循環(huán)結(jié)構(gòu)的運(yùn)行情況。
int i;for(i =0; i < n ; i++){
? /*時(shí)間復(fù)雜度為O(1)的程序*/? ? ?
}
對(duì)數(shù)階：
int count =1;?
while(count < n){
? count = count *2;
? /*時(shí)間復(fù)雜度為O(1)的程序*/? ?
}
因?yàn)槊看蝐ount*2后，距離結(jié)束循環(huán)更近了。也就是說有多少個(gè)2 相乘后大于n，退出循環(huán)。
數(shù)學(xué)公式：2x?= n ? ?--> ? ? x = log2n
因此這個(gè)循環(huán)的時(shí)間復(fù)雜度為O(logn)
平方階:
int i;
for(i =0; i < n ; i++){
? for(j =0; j < n ; j++){
? ? /*時(shí)間復(fù)雜度為O(1)的程序*/?
? ? }? ?
}
上面的程序中，對(duì)于對(duì)于內(nèi)層循環(huán)，它的時(shí)間復(fù)雜度為O(n)，但是它是包含在外層循環(huán)中，再循環(huán)n次，因此這段代碼的時(shí)間復(fù)雜度為O(n2)。
再來看一段程序：
int i;
for(i =0; i < n ; i++){
? for(j = i ; j < n ; j++){
? ? /*時(shí)間復(fù)雜度為O(1)的程序*/?
? ? }? ?
}
注意：上面的內(nèi)層循環(huán)j = i ;而不是0
因?yàn)閕 = 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-1)+...+1 =?n(n+1)/2=??n2/2?+?n/2
根據(jù)大O推導(dǎo)方法，保留最高階項(xiàng)，n2/2，然后去掉這個(gè)項(xiàng)相乘的常數(shù)，1/2
因此，這段代碼的時(shí)間復(fù)雜度為O(n2)
下面，分析調(diào)用函數(shù)時(shí)的時(shí)間復(fù)雜度計(jì)算方法：
首先，看一段代碼：
int i,j;
void function(int count){
? print(count);?
}
for(i =0; i < n ; i++){
? function (i)?
}
函數(shù)的時(shí)間復(fù)雜度是O(1)，因此整體的時(shí)間復(fù)雜度為O(n)。
假如function是這樣的：
void function(int count){
? int j;
? for(j = count ; j < n ;j++){
? ? ? ? /*時(shí)間復(fù)雜度為O(1)的程序*/ }
}
和第一個(gè)的不同之處在于把嵌套內(nèi)循環(huán)放到了函數(shù)中，因此最終的時(shí)間復(fù)雜度為O(n2)
常見的時(shí)間復(fù)雜度：
12 O(1) 常數(shù)階
2n+3 O(n) 線性階
3+2n+1 O(n2) 平方階
5log+20? O(log2n) 對(duì)數(shù)階
2n+3nlog+19 O(nlogn) nlog2n階
6+2
+3n+4 O(n3) 立方階
O(2n) 指數(shù)階
