轉載請注明出處：
http://blog.csdn.net/qq347198688/article/details/52725764
本文出自【何嘉龍的部落格】
前言
國慶小長假到了，不知道大家的國慶長假過得怎麼樣？在空間裡面看到同學都外出浪了，我表示很嫉妒啊。哎，作為一個死宅男，還是安安靜靜的在宿舍寫我的部落格還有刷劇吧。我是自動化專業，由于是非科班出生，又聽說大公司都比較重基礎，于是乎，我準備惡補下資料結構與算法分析，我看的是《大話資料結構》，希望把自己的基礎功打牢一點，進自己想進的公司吧。我也希望大家國慶能過得愉快！
時間複雜度
時間複雜度的定義
在進行算法分析時，語句總的執行次數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(n²)。我們分别給它們取了非官方的名稱，O(1)叫常數階、O(n)叫做線性階，O(n²)叫平方階，當然，還有其他的一些階，我們之後會介紹。
推導大O階方法
那麼如何分析一個算法的時間複雜度呢？即如何推導大O階呢？我們給出了下面的推導方法，基本上，這也就是總結前面我們舉的例子。
推導大O階：
1.用常數1取代運作時間後的所有加法常數。
2.在修改後的運作次數函數中，隻保留最高階項。
3.如果最高階存在且不是1，則去除與這個項相乘的常數。得到的結果就是大O階。
哈，仿佛是得到了遊戲攻略一樣，我們好像已經得到了一個推導算法時間複雜度的萬能公式。可事實上，分析一個算法的時間複雜度，沒有這麼簡單，我們還需要多看幾個例子。
常數階
首先順序結構的時間複雜度。下面這個算法，也就是高斯算法，為什麼時間複雜度不是O(3)，而是O(1)。
int sum = 0, n = 100; //執行1次
sum = (1 + n) * n / 2; //執行1次
printf("%d", sum); //執行1次 這個算法的運作次數函數是f(n) = 3.根據我們推導的大O階的方法，第一步就是把常數項3改為1,。在保留最高階項時發現，它根本沒有最高階項，是以這個算法的時間複雜度為O(1)。
另外，我們試想一下，如果這個算法當中的語句
sum = (1 + n) * n / 2
有10句，即：
int sum = 0, n = 100; //執行1次
sum = (1 + n) * n / 2; //執行第1次
sum = (1 + n) * n / 2; //執行第2次
sum = (1 + n) * n / 2; //執行第3次
sum = (1 + n) * n / 2; //執行第4次
sum = (1 + n) * n / 2; //執行第5次
sum = (1 + n) * n / 2; //執行第6次
sum = (1 + n) * n / 2; //執行第7次
sum = (1 + n) * n / 2; //執行第8次
sum = (1 + n) * n / 2; //執行第9次
sum = (1 + n) * n / 2; //執行第10次
printf("%d", sum); //執行1次 事實上無論n為多少，上面的兩段代碼就是3次和12次執行的差異。這種與問題的大小無關(n的多少)，執行時間恒定的算法，我們稱之為具有O(1)的時間複雜度，又叫常數階。
注意：不管這個常數是多少，我們都記作O(1)，而不能是O(3)、O(12)等其他任何數字，這是初學者常犯的錯誤。
對于分支結構而言，無論是真，還是假，執行的次數都是恒定的，不會随着n的變大而發生變化，是以單純的分支結構(不包含在循環結構裡)，其時間複雜度也是O(1)。
線性階
線性階的循環結構會複雜很多。要确定某個算法的階次，我們常常需要确定某個特定語句或某個語句集運作的次數。是以，我們要分析算法的複雜度，關鍵就是要分析循環結構的運作情況。
下面這段代碼，它的循環的時間複雜度為O(n)，因為循環體中的代碼必須要執行n次。
for(int i = 0; i < n; i++) {
//時間複雜度為O(1)的程式步驟序列
} 對數階
下面這段代碼，時間複雜度又是多少呢？
int count = 1;
while(count < n) {
count = count * 2;
//時間複雜度為O(1)的程式步驟序列
} 由于每次count乘以2之後，就距離n更近了一分。也就是說，有多少個2相乘後大于n，則會退出循環。由2的x次方=n，得到x=log₂n。是以這個循環的時間複雜度為O(logn)。
平方階
下面例子是一個循環嵌套，它的内循環剛才我們分析過了，時間複雜度為O(n)。
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
//時間複雜度為O(1)的程式步驟序列
}
} 而對于外層的循環，不過是内部這個時間複雜度為O(n)的語句，再循環n次。是以這段代碼的時間複雜度為O(n²)。
如果外循環的循環次數改為了m，時間複雜度就為O(m × n)。
for(int i = 0; i < m; i++) {
for(int j = 0; j < m; j++) {
//時間複雜度為O(1)的程式步驟序列
}
} 是以，我們可以總結出，循環的時間複雜度等于循環體的複雜度乘以該循環運作的次數。
那麼下面這個循環嵌套，他的時間複雜度又是多少呢？
for(int i = 0; i < n; i++) {
for(int j = i; j < n; j++) {
//時間複雜度為O(1)的程式步驟序列
}
} 當i = 0時，内循環執行了n次，當i = 1時，執行了n - 1次，依次類推，當i = n - 1時，執行了一次。是以總的執行次數為：
用我們推導大O階的方法，第一條，沒有加法常數不予考慮；第二條，隻保留最高階項，是以保留n²/2；第三條，去除這個項相乘的常數，也就是去除1/2，最終代碼的時間複雜度為O(n²)。
常見的時間複雜度
常見的時間複雜度如表所示：
所耗費的時間從小到大依次為：
空間複雜度
我們在寫代碼的時候，完全可以用空間來換取時間，比如說，要判斷某某年是不是閏年，你可能會花一點心思寫了一個算法，而且由于是一個算法，也就意味着，每次給一個年份，都是要通過計算得到是否是閏年的結果，還有另外一個辦法就是，事先建立一個有2050個元素的數組(年數略比現實多一點)，然後把所有的年份按下标的數字對應，如果是閏年，此數組項就是1，否則為0。這樣，所謂的判斷一年是否為閏年，就變成了查找數組的某一項值是多少的問題。此時，我們的運算已經是最小化了，但是硬碟上或者記憶體中需要存儲這2050個0和1。
這是一筆空間上的開銷來換取計算時間的小技巧。到底哪一個好，要看你用在什麼地方。
空間複雜度的定義
算法的空間複雜度通過計算算法所需的存儲控件實作，算法空間複雜度的計算公式為：S(n) = O(f(n))，其中，n為問題的規模，f(n)為語句關于n所占存儲空間的函數。
一般情況下，一個程式在機器上執行時，除了需要存儲程式本身的指令、常數、變量和輸入資料外，還需要存儲對資料操作的存儲單元。當不限定詞的使用“複雜度”的時候，通常指時間複雜度。