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

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

但是，在對算法進(jìn)行分析時(shí)，并沒有那么簡單。大部分情況下我們不能一眼看出算法執(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è)操作。所以我們對算法進(jìn)行時(shí)間上的分析時(shí)，往往需要使用到“大概”這個(gè)概念。但即使是推算算法耗費(fèi)的“大概”時(shí)間也是需要一些基本原則的，接下來我們就來看看如何推算算法的時(shí)間復(fù)雜度。（完整、嚴(yán)謹(jǐn)?shù)乃惴ǚ治霰容^復(fù)雜，本文只是寫一些“入門”的概念與分析方法）

即使在現(xiàn)實(shí)生活中，我們也會遇到類似于分析算法時(shí)間一樣的問題，比如有人問你多久能看完某本書，你可能會說“一個(gè)月之內(nèi)”而不是具體的“19天”，又比如有人問你最快多久能完成某項(xiàng)任務(wù)，你可能會說“至少3天”而不是“70小時(shí)”。而我們對算法進(jìn)行時(shí)間分析時(shí)也會用到類似的“技巧”，即不追求具體的時(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超過某個(gè)值后，c·f(N)總是至少比T(N)要大。忽略常數(shù)因子，即f(N)至少與T(N)一樣大。

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

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

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

舉例來說，N3比N2增長更快，因此N2=O(N3)與N3=Ω(N2)都是對的；2*N2與N2有著相同的相對增長率，因此N2=O(2*N2)與N2=Ω(2*N2)都是正確的。由于對算法進(jìn)行時(shí)間分析時(shí)往往考慮“最壞情況”，所以我們通常計(jì)算的是O(f(N))，即“上界”，俗稱“大O階”。

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

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

voidfunc ( unsignedint N )

{

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

? ? ? ? {

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

? ? ? ? }

}

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

? ? ? ?根據(jù)我們之前所說，所有運(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。再回顧之前所說，對于算法，我們一般都是計(jì)算大O階（即使這里我們算出了3N+1這樣“比較準(zhǔn)確”的時(shí)間花費(fèi)），因此接下來我們要對3N+1計(jì)算大O階。

但是3N+1的大O階有很多很多，比如O(N2)、O(N3)等等（因?yàn)镹2和N3的相對增長率肯定比3N+1大），究竟哪一個(gè)才是我們需要的？直覺告訴我們應(yīng)該是“最接近的”，即O(N)（根據(jù)定義一，顯然存在c=1000，n0=1這樣的情況使得N成為3N+1的大O階）。但是選擇這個(gè)“最接近”的大O階時(shí)有沒有什么原則呢？原則當(dāng)然還是有的，接下來我們就來說一說計(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，直接簡化為N^2

通過法則1中的加法規(guī)律（和法則2的簡化辦法），我們發(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)绾未蟠蠛喕摱囗?xiàng)式來獲得大O階。假設(shè)一個(gè)算法花費(fèi)時(shí)間3*N3+N2+3，那么根據(jù)法則2與法則3，我們可以直接得出其大O階為O(N3)。

?那么接下來的問題就只剩下如何得到那個(gè)原始的時(shí)間開銷了，比如我們知道了時(shí)間花費(fèi)是3*N2+3，那么我們可以得出大O階為O(N2)，但是問題在于3*N2+3該如何得到。其實(shí)這也是不難的?；仡欀拔覀兎治隽说哪莻€(gè)無意義的函數(shù)，我們就會發(fā)現(xiàn)，時(shí)間復(fù)雜度中最重要的就是“不確定次數(shù)的循環(huán)”，因?yàn)轫樞驁?zhí)行時(shí)不論有1000個(gè)還是10000個(gè)賦值、比較、算術(shù)運(yùn)算，最后計(jì)算大O階時(shí)都會變?yōu)槌?shù)項(xiàng)從而被忽略掉。至于為什么說是“不確定次數(shù)的”循環(huán)，原因就是如果次數(shù)確定，那么該循環(huán)也會變成一個(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)是會被忽略的。

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

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

　　比如

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

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

2.對于嵌套循環(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.對于順序結(jié)構(gòu)，只需要將各“部分”運(yùn)行時(shí)間相加即可。（對于IF/ELSE結(jié)構(gòu)，我們將整個(gè)IF/ELSE的運(yùn)行時(shí)間假定為其中最大的一種情況，這樣也許會比平均運(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.對于遞歸，如果其只是“遮了面紗”的循環(huán)，比如

intfunc (int? N )

{

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

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

}

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

最后總結(jié)，由于諸多現(xiàn)實(shí)原因，對于算法的時(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階的簡化原則將其簡化，得出算法的大O階。

雖然算法千千萬，但是算法的時(shí)間復(fù)雜度，大O階還是有一些規(guī)律的。什么規(guī)律呢？就是我們常見的大O階是可以列舉出來的。常見的大O階按照從好到壞，也就是增長率從低到高，列舉出來的話有：

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

? ? ? ? ?對數(shù)級logN

對數(shù)平方根級logN2

? ? ? ? ?線性級N

? ? ? ? ?N*logN

平方級N2

立方級N3

指數(shù)級2N

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

但是，對數(shù)級logN的復(fù)雜度是什么情況出現(xiàn)的呢？一般來說，如果一個(gè)算法用常數(shù)時(shí)間O(1)將問題的大小削減為其一部分，那么該算法就是O(logN)的。

雖然很多時(shí)候，一個(gè)算法的數(shù)據(jù)輸入就不得不耗費(fèi)Ω(N)的時(shí)間，因而整個(gè)算法最終的時(shí)間復(fù)雜度不會是O(logN)，但為了說明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)，接下來分析循環(huán)的次數(shù)，循環(huán)從High-Low=N-1開始，到High-Low=-1結(jié)束，每次循環(huán)后High-Low的值都會“折半”，符合我們之前說的判斷是否為logN級的條件，因而二分查找是O(logN)的。（即使不是削減為二分之一，而是三分之一、四分之一等，我們也記作logN級別）

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