評價算法的兩個重要依據(jù)——時間復雜度和空間復雜度郁惜。
時間復雜度：算法的時間復雜度堡距，它反映的不是算法的邏輯代碼到底被執(zhí)行了多少次，而是隨著輸入規(guī)模的增大兆蕉，算法對應的執(zhí)行總次數(shù)的一個變化趨勢羽戒。
- 我們來看一個??：
function traverse1(arr) {
var len = arr.length //執(zhí)行了1次
for(var i=0;i<len;i++) {
//var i=0; 執(zhí)行了1次
//i<len; 執(zhí)行了(n+1)次
//i++ 執(zhí)行了1次
console.log(arr[i]) //執(zhí)行了n次
}
}
function traverse2(arr) {
var outLen = arr.length
for(var i=0;i<outLen;i++) {
var inLen = arr[i].length
for(var j=0;j<inLen;j++) {
console.log(arr[i][j])
}
}
}
兩層循環(huán)代碼執(zhí)行的次數(shù)
做個求總執(zhí)行次數(shù) T(n)的加法看看：
//traverse1的代碼執(zhí)行次數(shù)
T(n) = 1 + n + 1 + (n+1) + n = 3n + 3
//traverse2的代碼執(zhí)行次數(shù)
T(n) = 1 + 1 + (n+1) + n + n + n + n*(n+1) + n*n + n*n = 3n^2 + 5n + 3
要想反映趨勢，那就簡單多了虎韵，直接抓主要矛盾就行半醉。我們可以嘗試對T(n) 做如下處理：
- 若
T(n)是常數(shù)，那么無腦簡化為1 - 若
T(n)是多項式劝术，比如3n^2 + 5n + 3缩多，我們只保留次數(shù)最高那一項呆奕，并且將其常數(shù)系數(shù)無腦改為1。
T(n) = 10 --> O(n) = 1
T(n) = 3n^2 + 5n + 3 --> O(n) = n^2
遍歷N維數(shù)組衬吆，需要 N 層循環(huán)梁钾，我們只需要關心其最內層那個循環(huán)體被執(zhí)行多少次就行了。
我們可以看出逊抡，規(guī)模為
n的一維數(shù)組遍歷時姆泻，最內層的循環(huán)會執(zhí)行n次，其對應的時間復雜度是O(n)冒嫡；規(guī)模為nn的二維數(shù)組遍歷時拇勃，最內層的循環(huán)會執(zhí)行nn次，其對應的時間復雜度是O(n^2)孝凌。
以此類推方咆，規(guī)模為
nm的二維數(shù)組最內層循環(huán)會執(zhí)行nm次，其對應的時間復雜度就是O(nm)蟀架；規(guī)模為nn*n的三維數(shù)組最內層循環(huán)會執(zhí)行n^3次瓣赂，因此其對應的時間復雜度就表示為O(n^3)。
空間復雜度：是對一個算法在運行過程中臨時占用存儲空間大小的量度片拍。和時間復雜度相似煌集，它是內存增長的趨勢。
- 常見的空間復雜度有
O(1)捌省、O(n)和O(n^2)苫纤。
理解空間復雜度，我們照樣來看一個??：
function traverse(arr) {
var len = arr.length
for(var i=0;i<len;i++) {
console.log(arr[i])
}
}
//在 traverse 中纲缓，占用空間的有以下變量:
//arr
//len
//i
后面盡管咱們做了很多次循環(huán)方面，但是這些都是時間上的開銷。循環(huán)體在執(zhí)行時色徘，并沒有開辟新的內存空間。因此操禀，整個
traverse函數(shù)對內存的占用量是恒定的褂策，它對應的空間復雜度就是O(1)。
下面我們來看另一個??颓屑，此時我想要初始化一個規(guī)模為 n 的數(shù)組斤寂，并且要求這個數(shù)組的每個元素的值與其索引始終是相等關系，我可以這樣寫：
function init(n) {
var arr = []
for(var i=0;i<n;i++) {
arr[i] = i
}
return arr
}
//在 init中揪惦，占用空間的有以下變量:
//n
//arr
//i
注意這里這個
arr遍搞，它并不是一個一成不變的數(shù)組。arr最終的大小是由輸入的 n 的大小決定的器腋，它會隨著n的增大而增大溪猿、呈一個線性關系钩杰。因此這個算法的空間復雜度就是O(n)。
由此我們不難想象诊县，假如需要初始化的是一個規(guī)模為
n*n的數(shù)組讲弄，那么它的空間復雜度就是O(n^2)啦。
