每一個優(yōu)秀的開發(fā)者腦中都有時間概念汞斧。他們想給用戶更多的時間讓用戶做他們想做的事情橙凳。他們通過最小化時間復(fù)雜度來實現(xiàn)這一目的这溅。
在你能理解程序的時間復(fù)雜度之前员舵，你需要了解最常使用它的地方：算法設(shè)計。
所以究竟什么是算法捉兴？
簡單來說蝎困，算法就是一系列被控制的步驟录语，你通過按序執(zhí)行這些步驟可以實現(xiàn)一些目標(biāo)或者產(chǎn)生一些輸出。讓我們以你祖母烘烤蛋糕的菜單為例子禾乘。等等澎埠，這也可以算作算法？當(dāng)然算始藕！
function 烘烤蛋糕(風(fēng)味, 加冰){
"
1. 烤箱預(yù)熱到350度（華氏）
2. 混合面粉蒲稳、酵母粉、鹽
3. 打發(fā)黃油和糖直到蓬松
4. 添加雞蛋
5. 將黃油和雞蛋混到面粉中
6. 添加牛奶和 " + 風(fēng)味 + "
7. 繼續(xù)攪拌
8. 放入盤中
9. 烘烤30分鐘
10." 如果要 加冰 伍派，加點(diǎn)冰 "
10. 大快朵頤
"
}
BakeCake('香草味', 要加冰) => 美味
算法在檢查時間復(fù)雜度時非常有用江耀，因為它可以以各種形態(tài)和大小出現(xiàn)。
就猶如你可以用100中不同的方式來切開一個派一樣诉植，你可以用多種不同的算法來解決同一個問題祥国。有的解決方法效率更高，比其他的方法需要更少的時間和更少的空間倍踪。
所以問題就是：我們怎么分析確認(rèn)哪一個算法效率最高系宫？
數(shù)學(xué)！程序的時間復(fù)雜度分析僅是一個極其簡單的數(shù)學(xué)方法建车，這種方法就是分析一個算法對于給定數(shù)量的輸入需要多長時間來完成任務(wù)扩借。這通常定義為大O表示法。
你會問缤至，什么是大 O 表示法潮罪？
如果你答應(yīng)不會放棄并且繼續(xù)閱讀，我會告訴你领斥。
大O表示法就是將算法的所有步驟轉(zhuǎn)換為代數(shù)項嫉到，然后排除不會對問題的整體復(fù)雜度產(chǎn)生較大影響的較低階常數(shù)和系數(shù)。
數(shù)學(xué)家可能會對我的“整體影響”假設(shè)有點(diǎn)沮喪月洛，但是開發(fā)人員為了節(jié)省時間何恶，這種方式更容易簡化問題：
規(guī)律 Big-O
2 O(1) --> 就是一個常數(shù)
2n + 10 O(n) --> n 對整體結(jié)果會產(chǎn)生最大影響
5n^2 O(n^2) --> n^2 具有最大影響
簡而言之，這個例子所要表達(dá)的就是：我們只關(guān)注表達(dá)式中對表達(dá)式最終結(jié)果會產(chǎn)生最大影響的因子嚼黔。（當(dāng)常數(shù)非常大而n很小的時候并不是這樣的细层，但是我們現(xiàn)在不要擔(dān)心這種情況）。
下面是一些常用的時間復(fù)雜度以及簡單的定義唬涧。更完整的定義可以翻閱維基百科疫赎。
**O(1)— **常量時間：給定一個大小為n的輸入，概算法只需要一步就可以完成任務(wù)碎节。
**O(log n)— **對數(shù)時間：給定大小為n的輸入捧搞，該算法每執(zhí)行一步，它完成任務(wù)所需要的步驟數(shù)目會以一定的因子減少。
**O(n)— **線性時間：給定大小為n的輸入胎撇，該算法完成任務(wù)所需要的步驟直接和n相關(guān)（1對1的關(guān)系）介粘。
O(n2)—二次方時間：給定大小為n的輸入，完成任務(wù)所需要的步驟是n的平方晚树。
**O(C^n)— **指數(shù)時間：給定大小為n的輸入碗短，完成任務(wù)所需要的步驟是一個常數(shù)的n次方（非常大的數(shù)字）。
有了這些概念题涨，我們一起來看看每一個復(fù)雜度完成任務(wù)所需要的步驟數(shù)：
let n = 16;
O (1) = 1 step "(awesome!)"
O (log n) = 4 steps "(awesome!)" -- assumed base 2
O (n) = 16 steps "(pretty good!)"
O(n^2) = 256 steps "(uhh..we can work with this?)"
O(2^n) = 65,536 steps "(...)"
如你所見，隨著算法復(fù)雜度的提高总滩，事情的復(fù)雜度也會以數(shù)量級增長纲堵。幸運(yùn)的是，計算機(jī)足夠強(qiáng)悍能夠相對快速的處理非常復(fù)雜的問題闰渔。
所以我們怎樣使用大O表示法來分析我們的代碼席函？
這里有一些簡便的例子向你展示怎么將這些知識運(yùn)用到已有的或者你自己寫的代碼。
在我們的例子中將使用如下的數(shù)據(jù)結(jié)構(gòu)：
var friends = {
'Mark' : true,
'Amy' : true,
'Carl' : false,
'Ray' : true,
'Laura' : false,
}
var sortedAges = [22, 24, 27, 29, 31]
O(1)— 常量時間
當(dāng)你知道key（objects）或者index（arrays）時進(jìn)行查找只需要一步就可以完成冈涧，所用時間就是一個常量茂附。
//If I know the persons name, I only have to take one step to check:
function isFriend(name){ //similar to knowing the index in an Array
return friends[name];
};
isFriend('Mark') // returns True and only took one step
function add(num1,num2){ // I have two numbers, takes one step to return the value
return num1 + num2
}
O (log n)— 對數(shù)時間
如果你知道在一個數(shù)組的哪一側(cè)進(jìn)行查找一個指定值時，你可以排除掉另外一半進(jìn)而節(jié)約時間督弓。
//You decrease the amount of work you have to do with each step
function thisOld(num, array){
var midPoint = Math.floor( array.length /2 );
if( array[midPoint] === num) return true;
if( array[midPoint] < num ) --> only look at second half of the array
if( array[midpoint] > num ) --> only look at first half of the array
//recursively repeat until you arrive at your solution
}
thisOld(29, sortedAges) // returns true
//Notes
//There are a bunch of other checks that should go into this example for it to be truly functional, but not necessary for this explanation.
//This solution works because our Array is sorted
//Recursive solutions are often logarithmic
//We'll get into recursion in another post!
?```
###O(n)— 線性時間
你必須通過遍歷整個數(shù)組（或者list）來完成這一任務(wù)营曼。單一**for循環(huán)**的時間復(fù)雜度通常都是線性的。此外數(shù)組方法比如**indexOf**的復(fù)雜度也是線性的愚隧。你不過是使用已經(jīng)抽象了的循環(huán)過程蒂阱。
//The number of steps you take is directly correlated to the your input size
function addAges(array){
var sum = 0;
for (let i=0 ; i < array.length; i++){ //has to go through each value
sum += array[i]
}
return sum;
}
addAges(sortedAges) //133
?```
O(n2)— 二次方時間
for循環(huán)嵌套的復(fù)雜度就是二次方的，因為你在一個線性操作里執(zhí)行另外一個線性操作（或者說： n*n =n2 ）
//The number of steps you take is your input size squared
function addedAges(array){
var addedAge = [];
for (let i=0 ; i < array.length; i++){ //has to go through each value
for(let j=i+1 ; j < array.length ; j++){ //and go through them again
addedAge.push(array[i] + array[j]);
}
}
return addedAge;
}
addedAges(sortedAges); //[ 46, 49, 51, 53, 51, 53, 55, 56, 58, 60 ]
//Notes
//Nested for loops. If one for loop is linear time (n)
//Then two nested for loops are (n * n) or (n^2) Quadratic!
O(2^n)—指數(shù)時間
指數(shù)復(fù)雜度通常出現(xiàn)在這種情況：你對數(shù)據(jù)了解甚少狂塘，但是你必須嘗試其所有的排列或者組合录煤。
//The number of steps it takes to accomplish a task is a constant to the n power
//實例
//嘗試找出長度為n的密碼中所以字符的組合
每當(dāng)你在編寫需要快速運(yùn)行的代碼時都應(yīng)該做代碼時間復(fù)雜度分析。
當(dāng)你有不同的方法來解決一個問題時荞胡，比較明智的做法是先實現(xiàn)一個能夠工作的解決方案妈踊。但是從長遠(yuǎn)來看，你需要一個盡可能快速且高效的解決方案泪漂。
為了幫助你完成解決問題的過程廊营，可以問這些簡單的問題：
1、這個可以解決問題嗎窖梁？是 =>
2赘风、你有時間考慮時間復(fù)雜度嗎
是 =>進(jìn)入第三步
否 =>稍后再回來，現(xiàn)在就跳轉(zhuǎn)到第六步
3纵刘、它覆蓋了所有的邊界條件邀窃？是 =>
4、我的復(fù)雜度已經(jīng)盡可能低？
否 =>重寫或者修改解決方案 -> 回到步驟1
是 =>進(jìn)入步驟5
5瞬捕、我的代碼D.R.Y(Don't Repeat Yourself) 是 =>
6鞍历、歡呼吧！
否 =>將代碼重構(gòu)到D.R.Y肪虎，然后再歡呼劣砍！
在任何（和所有）嘗試解決問題的時候都應(yīng)該進(jìn)行時間復(fù)雜度分析。長此以往將你成為優(yōu)秀的開發(fā)者扇救。你的同事和用戶都會因此而喜歡你刑枝。
再次說明，作為一個程序員你所面臨的絕大多數(shù)問題-不管是算法問題還是編程問題-沒有幾百個也有幾十個中解決辦法迅腔。他們在怎么解決問題的方法上會不一樣装畅，但是它們都能解決那個問題。
你可以在使用集合還是圖來存儲數(shù)據(jù)之間做出選擇沧烈。你也可以決定是否在團(tuán)隊項目中使用Angular掠兄、React或者Backbone。所有這些解決方案以不同的方式解決同一個問題锌雀。
鑒于這一點(diǎn)蚂夕，很難說某一個答案對于這些問題是“正確的”或者“最好的”。但是可以說對于給定的問題存在“更好”或者“更糟糕”的答案腋逆。
就我們前面的一個例子婿牍，如果你的團(tuán)隊中一半的人都有使用React的經(jīng)驗，那么使用React是一個更佳的答案惩歉，這個方案可以花更少的時間就能搭建起來并運(yùn)行起來牍汹。
描述一個更好的解決方案的能力通常源于一些類似的時間復(fù)雜度分析。
簡而言之柬泽，如果你嘗試解決一個問題慎菲，那就解決的完美一些。并且使用一些大O表示法來幫助你指出怎么做锨并。
最終總結(jié)：
**O(1)— **常數(shù)時間：該算法僅僅使用一步就可以完成任務(wù)
**O(log n)— **對數(shù)時間：該算法每執(zhí)行一步露该，它完成任務(wù)所需要的步驟數(shù)目會以一定的因子減少。
**O(n)— **線性時間：該算法完成任務(wù)所需要的步驟直接和n相關(guān)（1對1的關(guān)系）第煮。
**O(n2)— **二次方時間：完成任務(wù)所需要的步驟是n的平方解幼。
**O(C^n)— **指數(shù)時間：完成任務(wù)所需要的步驟是一個常數(shù)的n次方（非常大的數(shù)字）。
這里還有一些有用的資源包警，可以了解更多信息：
本文譯自 Algorithms in plain English: time complexity and Big-O notation
