js算法初步學習記錄
算法復雜度是我們來衡量一個算法執(zhí)行效率的一個度量標準谤草，算法復雜度通常主要有時間復雜度和空間復雜度兩種芹缔。時間復雜度就是指算法代碼在運行最終得到我們想要的結(jié)果時所消耗的時間，而空間復雜度則是指算法中用來存儲的數(shù)據(jù)結(jié)構(gòu)所占用的空間铝阐。往往一個時間復雜度比較低的算法擁有著較高的空間復雜度消玄，兩者是互相影響的荔燎，我們前面講解數(shù)據(jù)結(jié)構(gòu)中的一些例子和代碼也足以說明這一點贸诚。本文會簡單介紹一下用于描述算法的性能和復雜程度的大O表示法方庭。
此內(nèi)容由?小紅書（www.xiaohongshutuiguang.cn）轉(zhuǎn)載提供
我們先來看一段簡單的代碼厕吉，來幫助我們理解什么是大O表示法：
function increment(num) {
return ++num;
}
console.log(increment(1));
上面的代碼聲明了一個函數(shù)，然后調(diào)用它械念。這樣的代碼無論我們傳入的參數(shù)是什么头朱，它都會返回自增后的結(jié)果。也就是說該函數(shù)的執(zhí)行時間跟我們傳入的參數(shù)沒有任何關(guān)系龄减，執(zhí)行的時間都是X项钮。因此，我們稱該函數(shù)的復雜度是O(1)欺殿，常數(shù)的寄纵。
我們再來看看前面講過的順序搜索算法，我們直接把代碼拿過來用就好了脖苏。
//順序搜索
function sequentialSearch(array,item) {
for(var i = 0; i < array.length; i++) {
if(item === array[i]) {
return i;
};
};
return -1;
};
現(xiàn)在我們假設(shè)要搜索的數(shù)組是[1,2,3...9,10]，然后我們搜索1這個元素定踱，那么在第一次判斷時就能找到想要搜索的元素棍潘。那么我們這里先假設(shè)每執(zhí)行一次循環(huán)的開銷是1。那么我們還想搜索11崖媚，數(shù)組中沒有這個元素亦歉，sequentialSearch
就會執(zhí)行十次遍歷整個數(shù)組，發(fā)現(xiàn)沒有后返回-1畅哑。那么在最壞的情況下肴楷，數(shù)組的長度大小決定了算法的搜索時間。這樣的函數(shù)的時間復雜度就是O(n)荠呐，線性的赛蔫，這里的n就是數(shù)組的長度。
那么泥张，我們來稍微修改一下sequentialSearch讓它可以計算開銷：
//順序搜索
function sequentialSearch(array,item) {
var cost = 0;
for(var i = 0; i < array.length; i++) {
cost++;
if(item === array[i]) {
return i;
};
};
console.log(array.length,cost);
return -1;
};
sequentialSearch([1,2,3,4,5,6,7,8,9,10],11);
很簡單呵恢，就是加上了一個cost變量來計數(shù)。那么我們下面再來看看冒泡排序的時間復雜度是怎樣的媚创，這里我們不再浪費篇幅渗钉，直接在代碼中加入計數(shù)器：
function swap(array,index1,index2) {
var aux = array[index1];
array[index1] = array[index2];
array[index2] = aux;
}
function bubbleSort(array) {
var length = array.length;
var cost = 0;
for (var i = 0; i < length; i++) {
cost++;
for (var j = 0; j < length - 1; j++) {
cost++;
if(array[j] > array[j + 1]) {
swap(array,j,j+1);
}
}
}
console.log(length,cost);
}
bubbleSort([2,3,4,1,8,7,9,10]);
代碼本身沒什么好說的，我們發(fā)現(xiàn)钞钙，如果數(shù)組的長度是8鳄橘，那么我們排序所消耗的時間就是64，如果長度是10芒炼，消耗的時間就是100瘫怜。換句話說，冒泡排序的時間復雜度就是數(shù)組長度的平方焕议，也就是O(n2)宝磨。
上面的代碼是用js畫的一幅圖弧关，其中有一些常用的大O表示法所對應的時間復雜度，大家可以把代碼COPY到本地自行去看一下唤锉，這樣會才會對大O表示法有更好的理解世囊，為了偷點懶，也為了大家可以確實的自己去看一下圖標窿祥。我這里不會把圖給大家貼上的株憾。
