<big>版權(quán)聲明：本文為 Codeagles 原創(chuàng)文章，可以隨意轉(zhuǎn)載赶站，但必須在明確位置注明出處ａＢ病！贝椿！</big>
想要學(xué)會算法時間復(fù)雜度所计，那么就要先弄清楚幾個概念。
- 什么是算法時間復(fù)雜度团秽？
- 它有什么用呢主胧？
- 寫法記作 T(n)=O(f(n))
- T(n):語句執(zhí)行的總次數(shù)關(guān)于n的函數(shù)
- n：問題規(guī)模
- f(n):問題規(guī)模n的某個函數(shù)
- 用O()來體現(xiàn)算法時間復(fù)雜度的記法
時間復(fù)雜度的定義是：如果一個問題的規(guī)模是n叭首，解決這一問題所需算法所需要的時間是n的一個函數(shù)T(n)，則T(n)稱為這一算法的時間復(fù)雜度踪栋。
所謂算法時間復(fù)雜度就是一句話：算法中基本操作的執(zhí)行次數(shù)焙格。既然是T(n)的函數(shù)，隨著模塊n的增大夷都，算法執(zhí)行的時間的增長率和T(n)的增長率成正比眷唉，所以T(n)越小，算法的時間復(fù)雜度越低囤官，算法的效率越高冬阳。
那么它有什么用呢？剛才也說了党饮，可以通過f(n)的函數(shù)關(guān)系來評估算法的效率問題肝陪，說白了就是通過時間復(fù)雜度來看算法的好壞。
值得注意的是：有的算法中基本操作執(zhí)行次數(shù)不僅僅跟初始輸入的數(shù)據(jù)規(guī)模(n)有關(guān)刑顺，還和數(shù)據(jù)本身有關(guān)氯窍。例如一些排序算法，同樣n個待處理數(shù)據(jù)蹲堂，數(shù)據(jù)初始有序性不同狼讨，基本操作執(zhí)行次數(shù)也會不同。如果算法中有特殊要求柒竞，一般依照使得基本操作執(zhí)行次數(shù)最多的輸入來計算時間復(fù)雜度政供，即將最壞的情況最為算法時間復(fù)雜度的度量。
常見的是按復(fù)雜度的大小
有的人會對log2 n與log n做對比朽基，不理解這里為什么不一樣布隔，其實這兩個是一樣的也就是圖中第2個和第4個都是可以替換以2為底的對數(shù)形式。
對數(shù)時間
主條目：對數(shù)時間
若算法的T(n) = O(log n)踩晶，則稱其具有對數(shù)時間执泰。由于計算機(jī)使用二進(jìn)制的記數(shù)系統(tǒng)枕磁，對數(shù)常常以2為底（即log2 n渡蜻，有時寫作lg n）。然而计济，由對數(shù)的換底公式茸苇，loga n和logb n只有一個常數(shù)因子不同，這個因子在大O記法中被丟棄沦寂。因此記作O（log n）学密，而不論對數(shù)的底是多少，是對數(shù)時間算法的標(biāo)準(zhǔn)記法传藏∧迥海————維基
如何計算或者推導(dǎo)時間復(fù)雜度呢##
我們來分析一下常規(guī)做法：
- 確定算法中的基本操作以及問題的規(guī)模彤守。
- 根據(jù)基本操作執(zhí)行情況計算出規(guī)模n的函數(shù)f(n),并確定時間復(fù)雜度為T(n)=O( f(n)中增長最快的項/此項的系數(shù) ).
那么是什么意思呢?記住這個利器，這三句話即可哭靖。
- 用常數(shù)1替換所有加法常數(shù)具垫。
- 在修改后的運(yùn)行次數(shù)的函數(shù)中，只保留最高階項试幽。
- 如果最高階項不是1(例如O(1)),則把該項的系數(shù)除掉筝蚕，得到O
開始實戰(zhàn)##
這不是演戲，這不是演習(xí)铺坞，實戰(zhàn)之后就可以完全掌握概念了起宽。
第一類
看下面一對代碼，進(jìn)行分析：
int i=0,n=100; /*執(zhí)行了一次*/
i=n/2+n; /*執(zhí)行了一次*/
printf("i=%d",i); /*執(zhí)行了一次*/
那么不難分析出這段代碼一共執(zhí)行了3次济榨，那么時間復(fù)雜度就是O(3)坯沪，對吧？是不是很簡單腿短，如果真的是這樣屏箍，那就錯了，看我們的利器第一句橘忱，它是f(n)=3,所以應(yīng)該把3改為1赴魁，即O(1)。那么看下面這個：
int i=0,n=100; /*執(zhí)行了一次*/
i=n/2+n; /*執(zhí)行了一次*/
printf("i=%d",i); /*執(zhí)行了一次*/
printf("i=%d",i); /*執(zhí)行了一次*/
printf("i=%d",i); /*執(zhí)行了一次*/
printf("i=%d",i); /*執(zhí)行了一次*/
printf("i=%d",i); /*執(zhí)行了一次*/
這段代碼一共執(zhí)行了7次钝诚，那么時間復(fù)雜度為多少呢颖御，經(jīng)過上面的坑，這個應(yīng)該沒問題了凝颇，對潘拱，f(n)=7,把7改為1，即O(1)拧略。那么我們可以得知芦岂，這種代碼是具有恒定的執(zhí)行時間的，也就是代碼不會因為問題規(guī)模n的變化而發(fā)生變化垫蛆，所以我們都記為O(1).
第二類
void fun(int n)
{
int i=1,j=100;
while(i<n)
{
++j;
i+=2;
}
}
這個顯然n確定以后禽最，循環(huán)的開始結(jié)束都是與i有關(guān)的，且每次自增2袱饭，假設(shè)m次后結(jié)束循環(huán)羡棵，那么i應(yīng)該等于1+2m晦墙，那么就有n=1+2m妆距，因為我們要是執(zhí)行次數(shù)闯团，也就是解得m=(n-1)/2，此時我們可以看出n/2增長的是最快的項疹味，根據(jù)我們的法寶仅叫，我們需要把前面的系數(shù)除掉即可得到O帜篇，即(n/2)/(1/2)=n，得O(n).
有的為了更嚴(yán)謹(jǐn)?shù)耐茖?dǎo)诫咱，會對上面的式子進(jìn)行修改坠狡，即1+2m+K=n ，K為一個常數(shù)遂跟，因為循環(huán)的結(jié)束的時候往往i是稍稍大于n的逃沿，所以用一個K來修正這個式子，m=(n-1-K)/2,當(dāng)然因為K為常數(shù)幻锁，所以不會影響最終結(jié)果凯亮，畢竟有一個增長更快的家伙把它的影響干掉了。
做到這哄尔，是不是感覺很簡單了呢假消？那么我們趁熱打鐵進(jìn)行下一個。
int i=1;
while(i<n)
{
i=i*2;
}
推導(dǎo)時間復(fù)雜度岭接，最重要的就是要分析算法的執(zhí)行次數(shù)富拗。那么這段程序怎么分析呢？試著自己分析一下鸣戴，再來看吧啃沪。好啦，i起始值為1窄锅，每次都乘2创千，也就意味著每次都會距離n近一些，那么什么時候超過n而終止循環(huán)呢入偷？很簡單就是i22222...*2>n,那么假設(shè)k次之后大于n追驴，就有2^k=n,得出k=logn(上面說了還有些log2 n，都是一樣的疏之，以后都寫最簡形殿雪。)
馬上就要成功了，主要是練就分析算法和推導(dǎo)的思路锋爪。再來一個：
int i,j,x=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
x++;
}
這段代碼不用多想就知道丙曙，外循環(huán)執(zhí)行n次，內(nèi)循環(huán)也是執(zhí)行n几缭，則O(n^2).那么這段呢河泳？
int i,j,x=0;
for(i=0;i<n;i++)
{
for(j=i;j<n;j++)
x++;
}
由于當(dāng)i=0沃呢，時內(nèi)循環(huán)執(zhí)行了n次年栓，i=1時，執(zhí)行了n-1次薄霜，...i=n-1時某抓，執(zhí)行了1次纸兔，那么總次數(shù)為 n+(n-1)+(n-2)+..+1=n(n+1)/2,那么就是n2/2,即O(n2).
到這里基礎(chǔ)的就結(jié)束了，我想大家也應(yīng)該能看懂了吧否副，當(dāng)然還有一些比較復(fù)雜的算法汉矿，大家可以去自行試試，對于該文章不懂得可以在文章下面留言备禀，看到了我會回復(fù)的洲拇。
最后給大家做個練習(xí)吧。
i++;
function(n) /* 方法function(n)為時間復(fù)雜度O(n)*/
int k,m;
while(k<n)
{
function(n);
k++;
}
for(k=0;k<n;k++)
{
for(m=k;m<n;m++)
{
/*時間復(fù)雜度為O(1)的序列*/
}
}
小試牛刀曲尸，檢驗成果吧赋续，大家聯(lián)系完這個，函數(shù)調(diào)用的時間復(fù)雜度也被你征服了另患，對于這個題可以在評論區(qū)留下你的答案纽乱，并和大家分享吧！
