討論算法必提到O(),不太懂，嘗試?yán)斫庖幌隆?/p>
大O表示法
描述算法的性能和復(fù)雜度。常用O表示。一般考慮為cpu時(shí)間占用。
1.O(1)
算法執(zhí)行時(shí)間和參數(shù)無(wú)關(guān)，函數(shù)性能一樣，時(shí)間復(fù)雜度稱(chēng)為O(1)。
例：
function increaseNum(num){
return ++num
}
假如執(zhí)行時(shí)間為x，不管傳入任何值，執(zhí)行時(shí)間都是x。
2.O(n)
O(n),算法的執(zhí)行時(shí)間呈線(xiàn)性關(guān)系。如果你有 100 個(gè)元素，這種算法就要做 100 次工作。數(shù)據(jù)量翻倍那么運(yùn)行時(shí)間也翻倍。例子：線(xiàn)性查找。
function search(array, item) {
var cost = 0;
for (var i = 0; i < array.length; i++) {
cost++;
if (item === array[i]) {
return i;
}
}
}
時(shí)間花費(fèi)cost和輸入的array有關(guān)，呈線(xiàn)性關(guān)系。尋找item要把a(bǔ)rray遍歷一次。
3.O(n^2)
O(n^2 ), 有點(diǎn)慢。如果你有 100 個(gè)元素，這種算法需要做 100^2 = 10000 次工作。數(shù)據(jù)量 x 2 會(huì)導(dǎo)致運(yùn)行時(shí)間 x 4 (因?yàn)?2 的 2 次方等于 4)。例子：循環(huán)套循環(huán)的算法，比如插入排序。
//數(shù)組的交換，所以要引入index1，index2.數(shù)組內(nèi)部元素的交換
function swap(array, index1, index2) {
var aux = array[index1];
array[index1] = array[index2];
array[index2] = aux;
}
//冒泡排序O(n^2)
function bubbleSort(array) {
var length = array.length;
for (var i = 0; i < length; i++) {
for (var j = 0; j < length - 1; j++) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1);
}
}
}
return array;
}
大部分情況下你用直覺(jué)就可以知道一個(gè)算法的大 O 表示法。比如說(shuō)，如果你的代碼用一個(gè)循環(huán)遍歷你輸入的每個(gè)元素，那么這個(gè)算法就是 O(n)。如果是循環(huán)套循環(huán)，那就是 O(n^2)。如果 3 個(gè)循環(huán)套在一起就是 O(n^3)，以此類(lèi)推。
注意，大 O 表示法只是一種估算，當(dāng)數(shù)據(jù)量大的時(shí)候才有用。舉個(gè)例子，[插入排序](Insertion Sort/)的最糟情況運(yùn)行時(shí)間是 O(n^2)。 理論上來(lái)說(shuō)它的運(yùn)行時(shí)間比[歸并排序](Merge Sort/)要慢一些。歸并排序是 O(n log n)。但對(duì)于小數(shù)據(jù)量，插入排序?qū)嶋H上更快一些，特別是那些已經(jīng)有一部分?jǐn)?shù)據(jù)是排序好的數(shù)組。
如果你看完沒(méi)懂，也不要太糾結(jié)了。這種東西僅僅在比較兩種算法哪種更好的時(shí)候才有點(diǎn)用。但歸根結(jié)底，你還是要實(shí)際測(cè)試之后才能得出結(jié)論。而且如果數(shù)據(jù)量相對(duì)較小，哪怕算法比較慢，在實(shí)際使用也不會(huì)造成太大的問(wèn)題。
參考資料：
- 《學(xué)習(xí)javascript數(shù)據(jù)結(jié)構(gòu)和算法》
- 大 O 表示法
