問題：如何分析時間複雜度？
解析：當問題規模即要處理的數據增長時，基本操作要重複執行的次數必定也會增長，那麼我們關心地是這個執行次數以什麼樣的數量級增長。
我們用大O表示法表示下常見的時間複雜度量級：
常數階O(1) 線性階O(n) 對數階O(logn) 線性對數階O(nlogn) 平階O(n)
當然還有指數階和階乘階這種常極端的複雜度量級，我們就不討論了。
O(1)
傳說中的常數階的複雜度，這種複雜度無論數據規模n如何增長，計算時間是不變的。
const increment = n => n++
舉個簡單的例：
不管n如何增長，都不會影響到這個函數的計算時間，因此這個代碼的時間複雜度都是O(1)。
O(n)
線性複雜度，隨著數據規模n的增，計算時間也會隨著n線性增。
典型的O(n)的例就是線性查找。
const linearSearch = (arr, target) =>
{ for (let i = 0; i < arr.length; i++)
{
if (arr[i] === target)
{ return i
}
}
return -1
}
線性查找的時間消化與輸入的數組數量n成個線性例，隨著n規模的增大，時間也會線性增長。
O(logn)
對數複雜度，隨著問題規模n的增長，計算時間也會隨著n對數級增長。
典型的例是分查找法。
functions binarySearch(arr, target)
{ let max = arr.length - 1
let min = 0
while (min <= max) {
let mid = Math.floor((max + min) / 2)
if (target < arr[mid]) {
max = mid - 1
} else if (target > arr[mid])
{ min = mid + 1
} else {
return mid
}
}
return -1
}
在分查找法的代碼中，通過while循環，成 2 倍數的縮減搜索範圍，也就是說需要經過 log2^n 次即可跳出循環。
事實上在實際項目中， O(logn) 是個非常好的時間複雜度，比如當 n=100 的數據規模時，分查找只需要7次，線性查找需要100次，這對於計算機而言差距不，但是當有10億的數據規模的時候，分查找依然只需要30次，而線性查找需要驚人的10億次， O(logn) 時間複雜度的算法隨著數據規模的增大，它的優勢就越明顯。
O(nlogn)
線性對數複雜度，隨著數據規模n的增長，計算時間也會隨著n呈線性對數級增長。
const mergeSort = array =>
{ const len =
array.length if (len <
2) {
return len
}
const mid = Math.floor(len / 2)
const first = array.slice(0, mid)
const last = array.slice(mid)
return merge(mergeSort(fist), mergeSort(last))
function merge(left, right)
{ var result = [];
while (left.length && right.length)
這其中典型代表就是歸併排序
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
}
}
O(n)
平方級複雜度，典型情況是當存在雙重循環的時候，即把 O(n) 的代碼再嵌套循環遍，它的時間複雜度就是 O(n)了，代表應用是冒泡排序算法。
function
bubleSort(arra){ var
temp;
for(var
i=0;i<arra.length;i++){ for(var
j=0;j<arra.length-i-1;j++){
if(arra[j]>arra[j+1]){ temp
=arra[j];
arra[j]=arra[j+1];
arra[j+1]=temp;
}
}
};
以上就是小科今天整理提供的Web前端開發面試題，希望為Web前端同學提供了有用的面試素材，以後小科每日均會提供Python、Web及MySQL資料庫相關的習題。學習沒有捷徑，希望大家都能少走一些彎路，順利找到工作！