轉自：http://www.cnblogs.com/cj723/archive/2011/03/05/1971640.html
2.9 算法的時間複雜度
2.9.1 算法時間複雜度定義
在進行算法分析時，語句總的執行次數T(n)是關于問題規模n的函數，進而分析T(n)随n的變化情況并确定T(n)的數量級。算法的時間複雜度，也就是算法的時間量度，記作：T(n) = O(f(n))。它表示随問題規模n的增大，算法執行時間的增長率和f(n)的增長率相同，稱作算法的漸近時間複雜度，簡稱為時間複雜度。其中f(n)是問題規模n的某個函數。
這樣用大寫O()來展現算法時間複雜度的記法，我們稱之為大O記法。
一般情況下，随着n的增大，T(n)增長最慢的算法為最優算法。
顯然，由此算法時間複雜度的定義可知，我們的三個求和算法的時間複雜度分别為O(n)，O(1)，O(n2)。我們分别給它們取了非官方的名稱，O(1)叫常數階，O(n)叫線性階，O(n2)叫平方階，當然，還有其他的一些階，我們之後會介紹。
2.9.2 推導大O階方法
那麼如何分析一個算法的時間複雜度呢？即如何推導大O階呢？我們給出了下面的推導方法，基本上，這也就是總結前面我們舉的例子
推導大O階
1.用常數1取代運作時間中的所有加法常數。
2.在修改後的運作次數函數中，隻保留最高階項。
3.如果最高階項存在且不是1，則去除與這個項相乘的常數。
得到的結果就是大O階。
哈，仿佛是得到了遊戲攻略一樣，我們好像已經得到了一個推導算法時間複雜度的萬能公式。可事實上，分析一個算法的時間複雜度，沒有這麼簡單，我們還需要多看幾個例子。
2.9.3 常數階
首先順序結構的時間複雜度。下面這個算法，也就是剛才的第二種算法，為什麼時間複雜度不是O(3)，而是O(1)。
int sum = 0,n = 100; /*執行一次*/
sum = (1+n)*n/2; /*執行一次*/
printf("%d", sum); /*執行一次*/
這個算法的運作次數函數是f(n)=3。根據我們推導大O階的方法，第一步就是把常數項3改為1。在保留最高階項時發現，它根本沒有最高階項，是以這個算法的時間複雜度為O(1)。
另外，我們試想一下，如果這個算法當中的語句sum=(1+n)*n/2有10句，即：
事實上無論n為多少，上面的兩段代碼就是3次和12次執行的差異，這種與問題的大小無關（n的多少），執行時間恒定的算法，我們稱之為具有O(1)的時間複雜度，又叫常數階。
注意，不管這個常數是多少，我們都記作O(1)，而不能是O(3)、O(12)等其他任何數字。這是初學者常常犯的錯誤。
對于分支結構而言，無論是真，還是假，執行的次數都是恒定的，不會随着n的變大而發生變化，是以單純的分支結構（不包含在循環結構中），其時間複雜度也是O(1)。
2.9.4 線性階
循環結構就會複雜很多。要确定某個算法的階次，我們常常需要确定某個特定語句或某個語句集運作的次數。是以，我們要分析算法的複雜度，關鍵就是要分析循環結構的運作情況。
下面這段代碼，它的循環的時間複雜度為O(n)。因為循環體中的代碼須要執行n次。
int i;
for(i = 0; i < n; i++)
{
/*時間複雜度為O(1)的程式步驟序列*/
}
2.9.5 對數階
那麼下面的這段代碼，時間複雜度又是多少呢？
由于每次count乘以2之後，就距離n更近了一分。也就是說，有多少個2相乘後大于n，則會退出循環。由2x=n得到x=log2n。是以這個循環的時間複雜度為O(logn)。
2.9.6 平方階
下面的例子是一個循環嵌套，它的内循環剛才我們已經分析過，時間複雜度為O(n)。
而對于外層的循環，不過是内部這個時間複雜度為O(n)的語句，再循環n次。是以這段代碼的時間複雜度為O(n2)。
如果外循環的循環次數改為了m，時間複雜度就變為O(m×n)。
是以我們可以總結得出，循環的時間複雜度等于循環體的複雜度乘以該循環運作的次數。
那麼下面這個循環嵌套，它的時間複雜度是多少呢？
由于當i = 0時，内循環執行了n次，當i = 1時，執行了n－1次，……當i = n－1時，内循環執行了1次。是以總的執行次數為
用我們推導大O階的方法，第一條，沒有加法常數不予考慮；第二條，隻保留最高階項，是以保留n2/2；第三條，去除這個項相乘的常數，也就是去除1/2，最終這段代碼的時間複雜度為O(n2)。
從這個例子，我們也可以得到一個經驗，其實了解大O推導不算難，難的是對數列的一些相關運算，這更多的是考察你的數學知識和能力，是以想考研的朋友，要想在求算法時間複雜度這裡不失分，可能需要強化你的數學，特别是數列方面的知識和解題能力。
我們繼續看例子，對于方法調用的時間複雜度又如何分析。
int i,j;
function(i);
上面這段代碼調用一個函數function。
void function(int count)
print(count);
函數體是列印這個參數。其實這很好了解，function函數的時間複雜度是O(1)。是以整體的時間複雜度為O(n)。
假如function是下面這樣的：
事實上，這和剛才舉的例子是一樣的，隻不過把嵌套内循環放到了函數中，是以最終的時間複雜度為O(n2)。
下面這段相對複雜的語句：
它的執行次數
，根據推導大O階的方法，最終這段代碼的時間複雜度也是O(n2)。
常見的時間複雜度，按數量級遞增排列依次為：
常數階O(1){Hash表的查找}、
對數階O(log2n){二分查找}、
線性階O(n)、
線性對數階O(nlog2n){快速排序的平均複雜度}、
平方階O(n^2){冒泡排序}、
立方階O(n^3){求最短路徑的Floyd算法}、
k次方階O(n^k)、
指數階O(2^n){漢諾塔}。