這篇文章收錄在我的 Github 上 algorithms-tutorial摩骨，另外記錄了些算法題解奏赘，感興趣的可以看看胡野，轉(zhuǎn)載請注明出處。
(一) 基本概念
算法性能的好壞一般由內(nèi)部和外部因素所決定：
- 內(nèi)部：算法性能敬飒，所需要的時間邪铲，所需要的內(nèi)存空間
- 外部：輸入信息的大小，計算機的速度无拗，編譯器的質(zhì)量
時間復(fù)雜度使用來評判一個算法性能的好壞带到，主要測量的是算法內(nèi)部因素, 而常常忽略那些外部因素，或者認為它們是相同的英染。
那么算法性能的本質(zhì)是由增長率所決定的揽惹，我們一般用符號 O 來進行表示，當輸入函數(shù)參數(shù)個數(shù)為 n 是四康，通過 O 描述算法的性能搪搏。
比如一個簡單的冒泡排序，我們往往忽略單次比較所花費的時間闪金，而是通過當判斷的數(shù)目增多時疯溺，其判斷次數(shù)隨著數(shù)目的變化趨勢，也就是所謂的增長率哎垦。
(二) 常見的時間復(fù)雜度
| 時間復(fù)雜度 | 舉例 |
|---|---|
| O(1) | 彈出一個棧頂元素 |
| O(logn) | 二分查找 - 平衡樹 |
| O(n) | 線性查找 - 亂序查找 |
| O(n^2) | 冒泡排序 |
| O(n^3) | 聯(lián)立線性方程 |
| O(2^n) | 漢諾塔問題 |
| O(n!) | Travelling salesman |
常見的算法時間復(fù)雜度由小到大依次為：
Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2^n)＜Ο(n!)
例如：
由圖中我們可以看出囱嫩，當 n 趨于無窮大時， O(nlogn) 的性能顯然要比 O(n^2) 來的高
一般來說漏设，只要算法中不存在循環(huán)語句挠说，其時間復(fù)雜度就是 O(1)
而時間復(fù)雜度又分為三種：
- 最優(yōu)時間復(fù)雜度 (Best-Case)
- 平均時間復(fù)雜度 (Average-Case)
- 最差時間復(fù)雜度 (Worst-Case)
最差時間復(fù)雜度的分析給了一個在最壞情況下的時間復(fù)雜度情況，這往往比平均時間復(fù)雜度好計算愿题，而最優(yōu)時間復(fù)雜度一般沒什么用，因為沒人會拿一些特殊情況去評判這個算法的好壞蛙奖。
(三) 計算時間復(fù)雜度
1.對于一些簡單的輸入輸出語句或賦值語句(無循環(huán)語句)潘酗，近似認為需要 O(1) 時間
比如：
int x = 1;
x++;
2.對于順序結(jié)構(gòu)，需要依次執(zhí)行一系列語句所用時間可采用 "求和法則"
比如：
for(int i = 0; i < n; i++){
//do something
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
//do something
}
}
代碼中包含兩段循環(huán)雁仲，所以時間計算：n + n^2仔夺，所以時間復(fù)雜度為 O(n^2)
值得注意的是，下面這段代碼：
for(int i = 0; i < n; i++){
for(int j = i; j < n; j++){
//do something
}
}
對循環(huán)次數(shù)進行求和會發(fā)現(xiàn): n + (n-1) + ... + 1 = 1/2n^2 + 1/2*n攒砖，所以時間復(fù)雜度仍為 O(n^2)
3.對于判斷條件語句來說缸兔，一般是求它的最差時間復(fù)雜度
比如：
if(x == 2){
return false;
}else{
for(int i = 0; i < n; i++){
if(j == 0){
return true;
}
}
}
一共花費的時間為 ``1 + n * 1```日裙，所以時間復(fù)雜度為 O(n)
4.對數(shù)時間復(fù)雜度：
當每次操作都能將所需要檢測的元素減少一半時(即每次操作，未檢測元素減少一半)惰蜜，這樣的時間復(fù)雜度為 O(logn)
例如: 二分查找法
在一本英文字典書中找一個單詞昂拂，因為字典都是按英文首字母升序的，所以我們可以從中間頁數(shù)開始查找抛猖，如果首字母比中間頁來的小格侯，則范圍就鎖定在前半本書，然后在在取前半本書的中間來依次進行判斷财著，直到找到該單詞联四。
從上我們可以得出簡化計算時間復(fù)雜度的步驟:
- 找到執(zhí)行次數(shù)最多的語句
- 計算語句執(zhí)行次數(shù)的數(shù)量級
- 用大O來表示結(jié)果
最后需要說明的是：性能并不代表一切。還有一些需要權(quán)衡的
- 是否容易進行理解撑教、實現(xiàn)和調(diào)試
- 高效地利用時間和空間
所以朝墩，最大化性能并不一定可取，但時間復(fù)雜度仍然可以很好地比較不同算法之間的性能差異伟姐。
