所謂算法的“時間復(fù)雜度”，你可以將其理解為算法“要花費的時間量”。比如說，讓你用抹布將家里完完全全打掃一遍（看成算法吧……）大概要5個小時，那么你用抹布打掃家里的“時間復(fù)雜度”就是5個小時。
小編給你個福利，加群710 520 381 驗證 靈狐 有免費的C/C++資料可以領(lǐng)取，還能得到和大神一起討論學(xué)習(xí)的機會！
但是，在對算法進行分析時，并沒有那么簡單。大部分情況下我們不能一眼看出算法執(zhí)行完需要耗費多少時間，一方面是因為我們很難考慮執(zhí)行算法的具體機器在各種操作上花費的時間，因為不同機器的運算速度不同，同一機器執(zhí)行不同操作的所用時間也不一樣。另一方面是我們很難統(tǒng)計算法到底執(zhí)行了多少個“操作”，比如不起眼的a+=1其實算兩個操作。所以我們對算法進行時間上的分析時，往往需要使用到“大概”這個概念。但即使是推算算法耗費的“大概”時間也是需要一些基本原則的，接下來我們就來看看如何推算算法的時間復(fù)雜度。（完整、嚴(yán)謹(jǐn)?shù)乃惴ǚ治霰容^復(fù)雜，本文只是寫一些“入門”的概念與分析方法）
即使在現(xiàn)實生活中，我們也會遇到類似于分析算法時間一樣的問題，比如有人問你多久能看完某本書，你可能會說“一個月之內(nèi)”而不是具體的“19天”，又比如有人問你最快多久能完成某項任務(wù)，你可能會說“至少3天”而不是“70小時”。而我們對算法進行時間分析時也會用到類似的“技巧”，即不追求具體的時間耗費，而是追求“上界”或“下界”。
? ?為了找出“上界”與“下界”，我們先要使用兩個定義：
?1.如果存在正常數(shù)c和n0，使得當(dāng)N>=n0時T(N)<=c·f(N)，則記為T(N)=O(f(N))
2.如果存在正常數(shù)c和n0，使得當(dāng)N>=n0時T(N)>=c·f(N)，則記為T(N)=Ω(f(N))
第一個定義的意思就是：當(dāng)N超過某個值后，c·f(N)總是至少比T(N)要大。忽略常數(shù)因子，即f(N)至少與T(N)一樣大。
類似的，第二個定義意思就是：當(dāng)N超過某個值后，c·f(N)總是最多和T(N)一樣大。
其實這兩個定義就是為了比較兩個函數(shù)之間的“相對增長率”，比如1000x和x2，雖然x<1000時1000x>x2，但是x2以更快的速度增長，因此x2最終會更大。
當(dāng)我們說T(N)=O(f(N))時，其實就是說“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)都是正確的。由于對算法進行時間分析時往往考慮“最壞情況”，所以我們通常計算的是O(f(N))，即“上界”，俗稱“大O階”。
? ? ?正如文章開頭說的，相同的算法在不同的機器上也會有不同的運行時間，同一臺機器的不同操作也會有不同的時間開銷。因此，我們假設(shè)我們的“計算機”所有運算如加減乘除、比較、賦值等都是耗費相同時間的，并且不考慮內(nèi)存問題，從而后面討論算法時間復(fù)雜度時，我們不再帶單位，只關(guān)心“數(shù)值”。
? ? ? ?接下來，讓我們帶著現(xiàn)有的概念與知識，來計算一個簡單的函數(shù)可能花費的時間（也可以說時間復(fù)雜度，或者大O階）
voidfunc ( unsignedint N )
{
? ? ? ? for(inti =0; i < N ; ++i )
? ? ? ? {
? ? ? ? ? ? ? ? i = i ;
? ? ? ? }
}
? ? ? ?顯然這個函數(shù)并沒有什么意義，我們也只是拿來練練手算算時間開銷罷了。那么接下來就讓我們一步一步看看它要花費多少時間。
? ? ? ?根據(jù)我們之前所說，所有運算耗費相同時間且不帶單位，那么，初始化i花費1時間，每次循環(huán)需要執(zhí)行一次比較，一次賦值，一次自增總共3時間，N次循環(huán)即3N時間，加上定義i的1時間，算法花費的總時間是3N+1。再回顧之前所說，對于算法，我們一般都是計算大O階（即使這里我們算出了3N+1這樣“比較準(zhǔn)確”的時間花費），因此接下來我們要對3N+1計算大O階。
但是3N+1的大O階有很多很多，比如O(N2)、O(N3)等等（因為N2和N3的相對增長率肯定比3N+1大），究竟哪一個才是我們需要的？直覺告訴我們應(yīng)該是“最接近的”，即O(N)（根據(jù)定義一，顯然存在c=1000，n0=1這樣的情況使得N成為3N+1的大O階）。但是選擇這個“最接近”的大O階時有沒有什么原則呢？原則當(dāng)然還是有的，接下來我們就來說一說計算算法時間復(fù)雜度O()時的一些原則（和捷徑）。
? ? ? ? 首先，我們要確定三個關(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ù)項，比如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)是一個k次多項式，那么T(N)=O(N^k)。
法則2與法則3是我們常用的，因為算法的時間復(fù)雜度往往是一個多項式，而法則2和法則3告訴了我們?nèi)绾未蟠蠛喕摱囗検絹慝@得大O階。假設(shè)一個算法花費時間3*N3+N2+3，那么根據(jù)法則2與法則3，我們可以直接得出其大O階為O(N3)。
?那么接下來的問題就只剩下如何得到那個原始的時間開銷了，比如我們知道了時間花費是3*N2+3，那么我們可以得出大O階為O(N2)，但是問題在于3*N2+3該如何得到。其實這也是不難的?；仡欀拔覀兎治隽说哪莻€無意義的函數(shù)，我們就會發(fā)現(xiàn)，時間復(fù)雜度中最重要的就是“不確定次數(shù)的循環(huán)”，因為順序執(zhí)行時不論有1000個還是10000個賦值、比較、算術(shù)運算，最后計算大O階時都會變?yōu)槌?shù)項從而被忽略掉。至于為什么說是“不確定次數(shù)的”循環(huán)，原因就是如果次數(shù)確定，那么該循環(huán)也會變成一個常數(shù)項：
for(inti =0; i<10;++i );
? ? ? ? 不難發(fā)現(xiàn)這個循環(huán)的時間花費其實是固定的1+10+9=20，是一個常數(shù)，而常數(shù)項是會被忽略的。
? ? ? ? 那么對于次數(shù)不定的循環(huán)（假定循環(huán)次數(shù)都由算法的輸入?yún)?shù)N決定），那么我們有幾個很簡單的基本原則：
?1.對于循環(huán)，運行時間最多為其內(nèi)部語句的運行時間（比如4次運算）乘以循環(huán)次數(shù)（N）。
比如
for(inti =0; i < N ;++i );
的運行時間最多為1*N，即O(N)
2.對于嵌套循環(huán)，根據(jù)原則1，不難發(fā)現(xiàn)就是內(nèi)部循環(huán)的運行時間乘以外部循環(huán)次數(shù)（N）。
比如
for(inti =0; i < N ; ++i )
? ? for(intj =0; j < N ; ++j );
的運行時間就是N*N，即O(N2)
?3.對于順序結(jié)構(gòu)，只需要將各“部分”運行時間相加即可。（對于IF/ELSE結(jié)構(gòu)，我們將整個IF/ELSE的運行時間假定為其中最大的一種情況，這樣也許會比平均運行時間要大，但是保證了“上界”的要求）比如
for(inti =0; i < N ;++i );for(inti =0; i < N ; ++i )
? ? for(intj =0; j < N ; ++j );
的運行時間就是N+N*N=N^2+N，大O階為O(N^2)
?4.對于遞歸，如果其只是“遮了面紗”的循環(huán)，比如
intfunc (int? N )
{
? ? ? ? if( N<=1)return1;
? ? ? ? returnN*func ( N -1 );
}
?那么其運行時間就以其循環(huán)形式計算，得出N。但實際情況中遇到的遞歸往往是難以化簡為循環(huán)的，這時對遞歸的時間分析將比較復(fù)雜，本文不予討論。
最后總結(jié)，由于諸多現(xiàn)實原因，對于算法的時間分析我們往往只計算個大概，而計算這個大概時我們最在乎的是代表著最壞情況的“上界”，也即大O階。要想計算一個算法的大O階，我們首先要計算其大致的時間花費，比如一個循環(huán)N次的循環(huán)體中有不確定的常數(shù)c次運算，此時我們不計較c的具體大小，直接將該循環(huán)體時間花費記為N，然后根據(jù)計算大O階的簡化原則將其簡化，得出算法的大O階。
雖然算法千千萬，但是算法的時間復(fù)雜度，大O階還是有一些規(guī)律的。什么規(guī)律呢？就是我們常見的大O階是可以列舉出來的。常見的大O階按照從好到壞，也就是增長率從低到高，列舉出來的話有：
? ? ? ? ?常數(shù)級C
? ? ? ? ?對數(shù)級logN
對數(shù)平方根級logN2
? ? ? ? ?線性級N
? ? ? ? ?N*logN
平方級N2
立方級N3
指數(shù)級2N
稍加分析就會發(fā)現(xiàn)其實它們的順序就是函數(shù)增長率的順序，有了這個順序，我們就可以對一些算法的時間復(fù)雜度進行比較了。比如完成同一件事，一個算法是O(NlogN)，另一個算法是O(N^2)，那么顯然當(dāng)N很大時，前者比后者會快很多（觀察函數(shù)圖像也可以很明顯的發(fā)現(xiàn)這一點）。
但是，對數(shù)級logN的復(fù)雜度是什么情況出現(xiàn)的呢？一般來說，如果一個算法用常數(shù)時間O(1)將問題的大小削減為其一部分，那么該算法就是O(logN)的。
雖然很多時候，一個算法的數(shù)據(jù)輸入就不得不耗費Ω(N)的時間，因而整個算法最終的時間復(fù)雜度不會是O(logN)，但為了說明O(logN)的情況，我們假設(shè)算法的數(shù)據(jù)已經(jīng)輸入到了內(nèi)存中，那么作為O(logN)的典例就是二分查找（本例中假設(shè)數(shù)組已按從小到大排好順序，我們要找出某個數(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)部的運行時間為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ù)雜度（比如同一個算法用循環(huán)實現(xiàn)和遞歸實現(xiàn)的空間占用就會明顯不同）等，并且在復(fù)雜的算法計算中還會用到高等數(shù)學(xué)的極限思想與計算方法。有相關(guān)興趣的讀者可以自行搜索關(guān)于算法分析的其它內(nèi)容來了解。另外，對于不同的場景，算法的分析會有不同的要求，比如我們說忽略常數(shù)項，但如果這個常數(shù)項真的足夠大而機器又足夠慢，那么即使是常數(shù)項也不是隨便忽略的。
