所謂算法的“時(shí)間復(fù)雜度”，你可以將其理解為算法“要花費(fèi)的時(shí)間量”侣诺。比如說(shuō)抛人，讓你用抹布將家里完完全全打掃一遍（看成算法吧……）大概要5個(gè)小時(shí)叹洲，那么你用抹布打掃家里的“時(shí)間復(fù)雜度”就是5個(gè)小時(shí)。

小編給你個(gè)福利鲁纠，加群710 520 381 驗(yàn)證 靈狐 有免費(fèi)的C/C++資料可以領(lǐng)取总棵，還能得到和大神一起討論學(xué)習(xí)的機(jī)會(huì)！

但是改含，在對(duì)算法進(jìn)行分析時(shí)情龄，并沒(méi)有那么簡(jiǎn)單。大部分情況下我們不能一眼看出算法執(zhí)行完需要耗費(fèi)多少時(shí)間捍壤，一方面是因?yàn)槲覀兒茈y考慮執(zhí)行算法的具體機(jī)器在各種操作上花費(fèi)的時(shí)間骤视，因?yàn)椴煌瑱C(jī)器的運(yùn)算速度不同，同一機(jī)器執(zhí)行不同操作的所用時(shí)間也不一樣鹃觉。另一方面是我們很難統(tǒng)計(jì)算法到底執(zhí)行了多少個(gè)“操作”专酗，比如不起眼的a+=1其實(shí)算兩個(gè)操作。所以我們對(duì)算法進(jìn)行時(shí)間上的分析時(shí)盗扇，往往需要使用到“大概”這個(gè)概念笼裳。但即使是推算算法耗費(fèi)的“大概”時(shí)間也是需要一些基本原則的，接下來(lái)我們就來(lái)看看如何推算算法的時(shí)間復(fù)雜度粱玲。（完整、嚴(yán)謹(jǐn)?shù)乃惴ǚ治霰容^復(fù)雜拜轨，本文只是寫一些“入門”的概念與分析方法）

即使在現(xiàn)實(shí)生活中抽减，我們也會(huì)遇到類似于分析算法時(shí)間一樣的問(wèn)題，比如有人問(wèn)你多久能看完某本書橄碾，你可能會(huì)說(shuō)“一個(gè)月之內(nèi)”而不是具體的“19天”卵沉，又比如有人問(wèn)你最快多久能完成某項(xiàng)任務(wù)，你可能會(huì)說(shuō)“至少3天”而不是“70小時(shí)”法牲。而我們對(duì)算法進(jìn)行時(shí)間分析時(shí)也會(huì)用到類似的“技巧”史汗，即不追求具體的時(shí)間耗費(fèi)，而是追求“上界”或“下界”拒垃。

? ?為了找出“上界”與“下界”停撞，我們先要使用兩個(gè)定義：

?1.如果存在正常數(shù)c和n0，使得當(dāng)N>=n0時(shí)T(N)<=c·f(N)悼瓮，則記為T(N)=O(f(N))

2.如果存在正常數(shù)c和n0戈毒，使得當(dāng)N>=n0時(shí)T(N)>=c·f(N)，則記為T(N)=Ω(f(N))

第一個(gè)定義的意思就是：當(dāng)N超過(guò)某個(gè)值后横堡，c·f(N)總是至少比T(N)要大埋市。忽略常數(shù)因子，即f(N)至少與T(N)一樣大命贴。

類似的道宅，第二個(gè)定義意思就是：當(dāng)N超過(guò)某個(gè)值后食听，c·f(N)總是最多和T(N)一樣大。

其實(shí)這兩個(gè)定義就是為了比較兩個(gè)函數(shù)之間的“相對(duì)增長(zhǎng)率”污茵，比如1000x和x2樱报，雖然x<1000時(shí)1000x>x2，但是x2以更快的速度增長(zhǎng)省咨，因此x2最終會(huì)更大肃弟。

當(dāng)我們說(shuō)T(N)=O(f(N))時(shí)，其實(shí)就是說(shuō)“T(N)是在以不快于f(N)的速度增長(zhǎng)”零蓉，類似的T(N)=Ω(f(N))即“T(N)是在以不慢于f(N)的速度增長(zhǎng)”笤受。不難發(fā)現(xiàn)，O(f(N))就是T(N)的“上界”敌蜂，Ω(f(N))就是T(N)的“下界”箩兽。

舉例來(lái)說(shuō)，N3比N2增長(zhǎng)更快章喉，因此N2=O(N3)與N3=Ω(N2)都是對(duì)的汗贫；2*N2與N2有著相同的相對(duì)增長(zhǎng)率，因此N2=O(2*N2)與N2=Ω(2*N2)都是正確的秸脱。由于對(duì)算法進(jìn)行時(shí)間分析時(shí)往往考慮“最壞情況”落包，所以我們通常計(jì)算的是O(f(N))，即“上界”摊唇，俗稱“大O階”咐蝇。

? ? ?正如文章開頭說(shuō)的，相同的算法在不同的機(jī)器上也會(huì)有不同的運(yùn)行時(shí)間巷查，同一臺(tái)機(jī)器的不同操作也會(huì)有不同的時(shí)間開銷有序。因此，我們假設(shè)我們的“計(jì)算機(jī)”所有運(yùn)算如加減乘除岛请、比較旭寿、賦值等都是耗費(fèi)相同時(shí)間的，并且不考慮內(nèi)存問(wèn)題崇败，從而后面討論算法時(shí)間復(fù)雜度時(shí)盅称，我們不再帶單位，只關(guān)心“數(shù)值”后室。

? ? ? ?接下來(lái)微渠，讓我們帶著現(xiàn)有的概念與知識(shí)，來(lái)計(jì)算一個(gè)簡(jiǎn)單的函數(shù)可能花費(fèi)的時(shí)間（也可以說(shuō)時(shí)間復(fù)雜度咧擂，或者大O階）

voidfunc ( unsignedint N )

{

? ? ? ? for(inti =0; i < N ; ++i )

? ? ? ? {

? ? ? ? ? ? ? ? i = i ;

? ? ? ? }

}

? ? ? ?顯然這個(gè)函數(shù)并沒(méi)有什么意義逞盆，我們也只是拿來(lái)練練手算算時(shí)間開銷罷了。那么接下來(lái)就讓我們一步一步看看它要花費(fèi)多少時(shí)間松申。

? ? ? ?根據(jù)我們之前所說(shuō)云芦，所有運(yùn)算耗費(fèi)相同時(shí)間且不帶單位俯逾，那么，初始化i花費(fèi)1時(shí)間舅逸，每次循環(huán)需要執(zhí)行一次比較桌肴，一次賦值，一次自增總共3時(shí)間琉历，N次循環(huán)即3N時(shí)間坠七，加上定義i的1時(shí)間，算法花費(fèi)的總時(shí)間是3N+1旗笔。再回顧之前所說(shuō)彪置，對(duì)于算法，我們一般都是計(jì)算大O階（即使這里我們算出了3N+1這樣“比較準(zhǔn)確”的時(shí)間花費(fèi)）蝇恶，因此接下來(lái)我們要對(duì)3N+1計(jì)算大O階拳魁。

但是3N+1的大O階有很多很多，比如O(N2)撮弧、O(N3)等等（因?yàn)镹2和N3的相對(duì)增長(zhǎng)率肯定比3N+1大）潘懊，究竟哪一個(gè)才是我們需要的？直覺(jué)告訴我們應(yīng)該是“最接近的”贿衍，即O(N)（根據(jù)定義一授舟，顯然存在c=1000，n0=1這樣的情況使得N成為3N+1的大O階）贸辈。但是選擇這個(gè)“最接近”的大O階時(shí)有沒(méi)有什么原則呢释树？原則當(dāng)然還是有的，接下來(lái)我們就來(lái)說(shuō)一說(shuō)計(jì)算算法時(shí)間復(fù)雜度O()時(shí)的一些原則（和捷徑）裙椭。

? ? ? ? 首先，我們要確定三個(gè)關(guān)于大O階的法則：

?1.如果T(N)=O(f(N))署浩，G(N)=O(h(N))揉燃，那么T(N)+G(N)=max(O(f(N)) , O(h(N)))。T(N)*G(N)=O(f(N)*h(N))筋栋。

? ? ? ? 2.忽略時(shí)間花費(fèi)中的常數(shù)項(xiàng)炊汤，比如3*N^2+3，直接簡(jiǎn)化為N^2

通過(guò)法則1中的加法規(guī)律（和法則2的簡(jiǎn)化辦法）弊攘，我們發(fā)現(xiàn)N2=O(N2)抢腐，N=O(N)，那么N2+N=max(O(N2) , O(N)) = O(N2)襟交。因此迈倍，我們有了法則3：

?3.如果T(N)是一個(gè)k次多項(xiàng)式，那么T(N)=O(N^k)捣域。

法則2與法則3是我們常用的啼染，因?yàn)樗惴ǖ臅r(shí)間復(fù)雜度往往是一個(gè)多項(xiàng)式宴合，而法則2和法則3告訴了我們?nèi)绾未蟠蠛?jiǎn)化該多項(xiàng)式來(lái)獲得大O階。假設(shè)一個(gè)算法花費(fèi)時(shí)間3*N3+N2+3迹鹅，那么根據(jù)法則2與法則3卦洽，我們可以直接得出其大O階為O(N3)。

?那么接下來(lái)的問(wèn)題就只剩下如何得到那個(gè)原始的時(shí)間開銷了斜棚，比如我們知道了時(shí)間花費(fèi)是3*N2+3阀蒂，那么我們可以得出大O階為O(N2)，但是問(wèn)題在于3*N2+3該如何得到弟蚀。其實(shí)這也是不難的蚤霞。回顧之前我們分析了的那個(gè)無(wú)意義的函數(shù)粗梭，我們就會(huì)發(fā)現(xiàn)争便，時(shí)間復(fù)雜度中最重要的就是“不確定次數(shù)的循環(huán)”，因?yàn)轫樞驁?zhí)行時(shí)不論有1000個(gè)還是10000個(gè)賦值断医、比較滞乙、算術(shù)運(yùn)算，最后計(jì)算大O階時(shí)都會(huì)變?yōu)槌?shù)項(xiàng)從而被忽略掉鉴嗤。至于為什么說(shuō)是“不確定次數(shù)的”循環(huán)斩启，原因就是如果次數(shù)確定，那么該循環(huán)也會(huì)變成一個(gè)常數(shù)項(xiàng)：

for(inti =0; i<10;++i );

? ? ? ? 不難發(fā)現(xiàn)這個(gè)循環(huán)的時(shí)間花費(fèi)其實(shí)是固定的1+10+9=20醉锅，是一個(gè)常數(shù)兔簇，而常數(shù)項(xiàng)是會(huì)被忽略的。

? ? ? ? 那么對(duì)于次數(shù)不定的循環(huán)（假定循環(huán)次數(shù)都由算法的輸入?yún)?shù)N決定）硬耍，那么我們有幾個(gè)很簡(jiǎn)單的基本原則：

?1.對(duì)于循環(huán)垄琐，運(yùn)行時(shí)間最多為其內(nèi)部語(yǔ)句的運(yùn)行時(shí)間（比如4次運(yùn)算）乘以循環(huán)次數(shù)（N）。

　　比如

for(inti =0; i < N ;++i );

　　的運(yùn)行時(shí)間最多為1*N经柴，即O(N)

2.對(duì)于嵌套循環(huán)狸窘，根據(jù)原則1，不難發(fā)現(xiàn)就是內(nèi)部循環(huán)的運(yùn)行時(shí)間乘以外部循環(huán)次數(shù)（N）坯认。

　　比如

for(inti =0; i < N ; ++i )

? ? for(intj =0; j < N ; ++j );

的運(yùn)行時(shí)間就是N*N翻擒，即O(N2)

?3.對(duì)于順序結(jié)構(gòu)，只需要將各“部分”運(yùn)行時(shí)間相加即可牛哺。（對(duì)于IF/ELSE結(jié)構(gòu)陋气，我們將整個(gè)IF/ELSE的運(yùn)行時(shí)間假定為其中最大的一種情況，這樣也許會(huì)比平均運(yùn)行時(shí)間要大引润，但是保證了“上界”的要求）比如

for(inti =0; i < N ;++i );for(inti =0; i < N ; ++i )

? ? for(intj =0; j < N ; ++j );

　　的運(yùn)行時(shí)間就是N+N*N=N^2+N巩趁，大O階為O(N^2)

?4.對(duì)于遞歸，如果其只是“遮了面紗”的循環(huán)淳附，比如

intfunc (int? N )

{

? ? ? ? if( N<=1)return1;

? ? ? ? returnN*func ( N -1 );

}

　　?那么其運(yùn)行時(shí)間就以其循環(huán)形式計(jì)算晶渠，得出N凰荚。但實(shí)際情況中遇到的遞歸往往是難以化簡(jiǎn)為循環(huán)的，這時(shí)對(duì)遞歸的時(shí)間分析將比較復(fù)雜褒脯，本文不予討論便瑟。

最后總結(jié)，由于諸多現(xiàn)實(shí)原因番川，對(duì)于算法的時(shí)間分析我們往往只計(jì)算個(gè)大概到涂，而計(jì)算這個(gè)大概時(shí)我們最在乎的是代表著最壞情況的“上界”，也即大O階颁督。要想計(jì)算一個(gè)算法的大O階践啄，我們首先要計(jì)算其大致的時(shí)間花費(fèi)，比如一個(gè)循環(huán)N次的循環(huán)體中有不確定的常數(shù)c次運(yùn)算沉御，此時(shí)我們不計(jì)較c的具體大小屿讽，直接將該循環(huán)體時(shí)間花費(fèi)記為N，然后根據(jù)計(jì)算大O階的簡(jiǎn)化原則將其簡(jiǎn)化吠裆，得出算法的大O階伐谈。

雖然算法千千萬(wàn)，但是算法的時(shí)間復(fù)雜度试疙，大O階還是有一些規(guī)律的诵棵。什么規(guī)律呢？就是我們常見(jiàn)的大O階是可以列舉出來(lái)的祝旷。常見(jiàn)的大O階按照從好到壞履澳，也就是增長(zhǎng)率從低到高，列舉出來(lái)的話有：

? ? ? ? ?常數(shù)級(jí)C

? ? ? ? ?對(duì)數(shù)級(jí)logN

對(duì)數(shù)平方根級(jí)logN2

? ? ? ? ?線性級(jí)N

? ? ? ? ?N*logN

平方級(jí)N2

立方級(jí)N3

指數(shù)級(jí)2N

稍加分析就會(huì)發(fā)現(xiàn)其實(shí)它們的順序就是函數(shù)增長(zhǎng)率的順序怀跛，有了這個(gè)順序距贷，我們就可以對(duì)一些算法的時(shí)間復(fù)雜度進(jìn)行比較了。比如完成同一件事吻谋，一個(gè)算法是O(NlogN)忠蝗，另一個(gè)算法是O(N^2)，那么顯然當(dāng)N很大時(shí)滨溉，前者比后者會(huì)快很多（觀察函數(shù)圖像也可以很明顯的發(fā)現(xiàn)這一點(diǎn)）什湘。

但是长赞，對(duì)數(shù)級(jí)logN的復(fù)雜度是什么情況出現(xiàn)的呢晦攒？一般來(lái)說(shuō)，如果一個(gè)算法用常數(shù)時(shí)間O(1)將問(wèn)題的大小削減為其一部分得哆，那么該算法就是O(logN)的脯颜。

雖然很多時(shí)候，一個(gè)算法的數(shù)據(jù)輸入就不得不耗費(fèi)Ω(N)的時(shí)間贩据，因而整個(gè)算法最終的時(shí)間復(fù)雜度不會(huì)是O(logN)栋操，但為了說(shuō)明O(logN)的情況闸餐，我們假設(shè)算法的數(shù)據(jù)已經(jīng)輸入到了內(nèi)存中，那么作為O(logN)的典例就是二分查找（本例中假設(shè)數(shù)組已按從小到大排好順序矾芙，我們要找出某個(gè)數(shù)在數(shù)組中的位置）：

intBinarySearch (constintA[] ,intX,intN )//? X為要找的元素舍沙，N為數(shù)組大小{? ? ? ? ? intLow=0,High=N-1,Mid;

? ? ? ? ? while( Low <= High )

? ? ? ? ? {

? ? ? ? ? ? ? ? Mid= ( Low + High ) /2;

? ? ? ? ? ? ? ? if( A[ Mid ] < X )

? ? ? ? ? ? ? ? ? ? ? Low = Mid +1;

? ? ? ? ? ? ? ? elseif( A[ Mid ] > X )

? ? ? ? ? ? ? ? ? ? ? High = Mid -1;

? ? ? ? ? ? ? ? elsereturn? Mid;

? ? ? ? ? ? }

}

顯然，循環(huán)體內(nèi)部的運(yùn)行時(shí)間為O(1)剔宪，接下來(lái)分析循環(huán)的次數(shù)拂铡，循環(huán)從High-Low=N-1開始，到High-Low=-1結(jié)束葱绒，每次循環(huán)后High-Low的值都會(huì)“折半”感帅，符合我們之前說(shuō)的判斷是否為logN級(jí)的條件，因而二分查找是O(logN)的地淀。（即使不是削減為二分之一失球，而是三分之一、四分之一等帮毁，我們也記作logN級(jí)別）

文章寫到這实苞，相信讀者對(duì)于基本的算法分析已經(jīng)有了概念。但是算法分析并不只是這些東西作箍，比如我們一直沒(méi)有提到的類似于O()和Ω()的θ()硬梁，還有算法的空間復(fù)雜度（比如同一個(gè)算法用循環(huán)實(shí)現(xiàn)和遞歸實(shí)現(xiàn)的空間占用就會(huì)明顯不同）等，并且在復(fù)雜的算法計(jì)算中還會(huì)用到高等數(shù)學(xué)的極限思想與計(jì)算方法胞得。有相關(guān)興趣的讀者可以自行搜索關(guān)于算法分析的其它內(nèi)容來(lái)了解荧止。另外，對(duì)于不同的場(chǎng)景阶剑，算法的分析會(huì)有不同的要求跃巡，比如我們說(shuō)忽略常數(shù)項(xiàng)，但如果這個(gè)常數(shù)項(xiàng)真的足夠大而機(jī)器又足夠慢牧愁，那么即使是常數(shù)項(xiàng)也不是隨便忽略的素邪。