在 Day 1 我們講到的複雜度表示都是指時間複雜度,在輸入的參數越多越大的情況下,所要執行的步驟(執行所需花費的時間)的增長趨勢。
我們也可以使用 Big O notation 来表示空間複雜度。
空間複雜度指的是在輸入的參數越多越大的情況下,執行該演算法所需要記憶體空間的增長趨勢。
空間複雜度考慮的是執行演算法時所需要的記憶體,不考慮輸入的參數的大小。
null
、undefined
等等,空間複雜度是 O(1) (constant space)。function sum(arr) {
let total = 0;
for (let i = 0; i < arr.length; i++) {
total += arr[i];
}
return total;
}
我們來看上面的函式,宣告 total
變數存數字,在迴圈中反覆加總,最後回傳 total
。
就算 arr
參數本身長度無限大,影響的只有時間複雜度。函式裡面只有用到 total
與 i
這兩個數字變數,所以此算法的空間複雜度是 O(1)。
function double(arr) {
let newArr = [];
for (let i = 0; i < arr.length; i++) {
newArr.push(arr[i] * 2);
}
return newArr;
}
把輸入的陣列內元素全部乘以 2,最後回傳一個新的陣列。
在這個函式,輸入的陣列越長,newArr
也會越長,所需的空間當然也越多,所以空間複雜度是 O(n)。