概述
執(zhí)行效率是考量一個算法是否高效的主要指標(biāo)藻雌。然而時間、空間復(fù)雜度又是衡量算法執(zhí)行效率的主要維度
一疹吃、事后統(tǒng)計法的局限
以前通過統(tǒng)計蹦疑、監(jiān)控實際代碼的運(yùn)行就能夠獲取算法執(zhí)行的時間和占用的內(nèi)存大小西雀。這種事后統(tǒng)計方法雖然能夠評估算法的執(zhí)行效率萨驶，但還是存在諸多缺陷。
-
測試結(jié)果非常依賴測試環(huán)境
測試環(huán)境中硬件配置的不同對測試結(jié)果會產(chǎn)生很大的影響艇肴。
-
測試結(jié)果受數(shù)據(jù)規(guī)模的影響較大
對于同一個算法而言腔呜，測試數(shù)據(jù)量的大小不同，其所得出的性能測試結(jié)果也會不同再悼。
二核畴、大 O復(fù)雜度表示法
如下一段代碼：
public int sum(int n){
1 int sum = 0;
2 for(int i = 0; i<n ; i++){
3 sum = sum +1;
}
return sum;
}
假設(shè)每一段代碼的執(zhí)行時間單位為Ｔ，那么第１行代碼執(zhí)行時間為Ｔ冲九，第３行代碼由于執(zhí)行了ｎ次谤草，那么執(zhí)行時間為ｎＴ所以這段代碼的總執(zhí)行時間為（ｎ＋１）Ｔ，由此可知：所有代碼的執(zhí)行時間T(n)與每行代碼的執(zhí)行次數(shù)n成正比莺奸。
接下來再看一段代碼
public int sum(int n){
1 int sum = 0;
2 for (int i = 0 ; i<= n ; ++i){
3 for (int j = 0 ; j<= n ; ++j){
4 sum = sum + i*j;
}
}
return sum;
}
這里每行代碼的執(zhí)行時間單位仍舊為T丑孩，那么第1行代碼的執(zhí)行時間為T，第4行代碼由于執(zhí)行了n2次灭贷，所以執(zhí)行時間為n2T温学。因此，整段代碼的執(zhí)行時間為：（n2+1）T 甚疟。
將以上規(guī)律總結(jié)成一個公式仗岖，就是我們所知的大O表達(dá)式。
T(n) = O ( f (n) )
其中：T(n)代表代碼所執(zhí)行的時間览妖；n表示數(shù)據(jù)規(guī)模的大性簟；f(n)表示每行代碼執(zhí)行的次數(shù)總和讽膏。而公式中的O則表明了代碼的執(zhí)行時間T(n)與 f(n) 表達(dá)式成正比檩电。
大O復(fù)雜度分析表示法，并不具體表示代碼真正的執(zhí)行時間，而是表示代碼執(zhí)行時間隨數(shù)據(jù)規(guī)模增長的變化趨勢是嗜，一般叫作漸進(jìn)時間復(fù)雜度（asymptotic time complexity)愈案，簡稱時間復(fù)雜度。同時鹅搪，當(dāng)n趨于無限大的時候站绪，我們就可以忽略公式中的低階、常量丽柿、與系數(shù)三部分恢准。只需記錄一個最大的量級，如 T(n) = O(2n2 + 2n +3) 我們省略掉其中的低階甫题、常量馁筐、與系數(shù)所得出的最終結(jié)果為：T(n) = O(n2)。因此以上兩段代碼的時間復(fù)雜度就可以記為 ： T(n) = O(n) 坠非；T(n) = O(n2)敏沉。
三、時間復(fù)雜度分析
-
只關(guān)注循環(huán)執(zhí)行次數(shù)最多的一段代碼：
關(guān)于這一點(diǎn)炎码，之前的代碼示列就是很好的說明盟迟，這里不再贅述。
-
加法法則：總復(fù)雜度等于量級最大的那段代碼的復(fù)雜度
比如如下一段代碼：
public int sum(int n){ int sumOne = 0; for (int i = 0; i <= 1000 ; ++i){ 1 sumOne += i; } int sumTwo = 0; for (int i= 0; i< n ; ++i){ 2 sumTwo += i; } int sumThree = 0; for (int i = 0; i< n ; ++i){ for (int j = 0 ; j < n ;++j){ 3 sumThree = sumThree + i *j; } } return sumOne + sumTwo + sumThree; }這段代碼共分為三個部分潦闲，分別求sumOne攒菠、sumTwo、sumThree歉闰。我們可以分別解析每一個部分的時間復(fù)雜度辖众，然后再從他們之中選取一個量級最大的作為整段代碼的復(fù)雜度。
第一段代碼執(zhí)行了1000次和敬，所以其代表的是一個常量級的執(zhí)行時間凹炸，跟n的規(guī)模無關(guān)，可以將其忽略掉概龄。
第二段代碼和第三段代碼分別執(zhí)行了 n 次和 n2次还惠，所以他們的時間復(fù)雜度分別為O(n) 和O(n2)。
綜合這三段代碼的時間復(fù)雜度私杜，我們?nèi)∑渲凶畲蟮牧考壊霞敲凑未a的復(fù)雜度就為：O(n2)
因此將上述這個公式抽象一下就可以得出：
如果：T1(n) = O(f(n))，T2(n)=O(g(n))衰粹；那么 T(n) = T1(n)+T2(n) = max(O(f(n)),O(g(n)))=O(max(f(n),g(n)))
-
乘法法則：嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積
如果T1(n) = O(f(n))锣光，T2(n) = O(g(n))；那么 T(n) = T1(n) x T2(n) = O(f(n)) x O(g(n) = O(f(n) x g(n))
public int sum(int n){
int result = 0;
for (int i = 0 ; i < n ;++i){
1 result = result + subSum(n);
}
return result;
}
public int subSum(int n){
int subSum = 0;
for (int j = 0 ; j < n ; ++j){
2 subSum += j;
}
return subSum;
}
其中：第一段铝耻，第二段代碼都是執(zhí)行了n次誊爹，時間復(fù)雜度都是 T(n) = O(n)蹬刷。但由于第二段代碼是嵌套在第一段代碼之中執(zhí)行的，因此整個代碼的時間復(fù)雜度應(yīng)為：T(n) = T1(n) x T2(n) = O(n) x O(n) = O(n2)
四频丘、常見時間復(fù)雜度
?
| 多項式量級 | 非多項式量級 |
|---|---|
| 常量階O(1) | 指數(shù)階O(2n) |
| 對數(shù)階O(logn) | 階乘階O(n!) |
| 線性階O(n) | |
| 線性對數(shù)階O(nlogn) | |
| 平方階O(n2)办成、立方階O(n3)、··· 搂漠、k次方階O(nk) |
-
常量階 O(1)
一般來說迂卢，只要算法中不存在循環(huán)語句、遞歸語句桐汤、即使有成千上萬行代碼而克，其時間復(fù)雜度仍舊是O(1)
-
對數(shù)階O(logn)，線性對數(shù)階O(nlogn)
int i = 1; while( i <= n){ i = i * 2; }如上一段代碼中怔毛，i 的取值為 20员萍， 21， 22拣度，···· 碎绎， 2x-1， 2x 成等比隊列蜡娶。要想知道這段代碼執(zhí)行了多少次混卵，求出 2x = n 的結(jié)果就行。 x = log2n窖张，所以這段代碼的時間復(fù)雜度就是 O( log2n)，這里忽視掉底數(shù)蚁滋，那么所有的對數(shù)階時間復(fù)雜度可以表示為O(logn)宿接。
-
O(m+n)、O(m * n)
public int sum(int m , int n){ int sumOne = 0; for (int i = 0 ; i<= m ; ++i){ sumOne += m; } int sumTwo = 0; for (int j = 0 ; j<= n ; ++j){ sumTwo += j; } return sumOne+sumTwo; }上述代碼中辕录，復(fù)雜度取決于兩個數(shù)據(jù)規(guī)模 m 與 n睦霎，因此無法事先評估m(xù) 與 n 誰的量級更大，因此加法法則在這里不適用走诞。因此上段代碼的時間復(fù)雜度即為O(m+n)副女。但是乘法法則依舊適用：T1(m) x T2(n) = O(f(m) x f(n))。
五蚣旱、空間復(fù)雜度分析
空間復(fù)雜度就是漸進(jìn)空間復(fù)雜度（asymptotic space complexity）,表示算法的存儲空間與數(shù)據(jù)規(guī)模之間的增長關(guān)系碑幅。
public void initArray(int n){
1 int[] arr = new int[n];
for (int i = 0 ; i<= n ; ++i){
arr[i] = i * i;
}
}
如上述代碼所示，我們在第一行代碼中申請了一個大小為n的int類型數(shù)組塞绿，除此之外其他的代碼都沒有占據(jù)更多的空間沟涨，因此整段代碼的空間復(fù)雜度就是O(n)，相對于時間復(fù)雜度而言异吻，空間復(fù)雜度的分析要更為簡單裹赴。
