時間複雜度 與 空間複雜度

同一個演算法在不同等級的電腦上跑，效率可能會有所不同，我們可以透過比較科學的方式，就是計算時間複雜度(Time Complexity)與空間複雜度(Space Complexity)來判斷演算法好壞。

時間複雜度

衡量程式執行的速度

介紹

時間複雜度可以使用Big O Notation來展示複雜度的趨勢，Big-Ο代表演算法時間函式的上限(Upper bound)，而在最壞的狀況下，演算法的執行時間不會超過Big-Ο。

那該如何計算Big O Notation，有三個規則:

• 常數可忽略不計
• 取最大次方
• Log底數可忽略不計

假設我們要求f(n) = 3n+2這段方程式的時間複雜度，根據上面所述規則，將常數部分去掉，根據漸進分析，在n變得非常大時，常數部分就變得微不足道，於是取得時間複雜度為O(n)。

以下為常見時間複雜度，接下來會一一舉例。

Big O Notation	別名	常見演算法
$O(1)$	常數	陣列讀取
$O(n)$	線性	Linear search
$O(logn)$	對數(Logarithmic )	二分搜尋法
$O(nlogn)$	線性	堆積排序，合併排序
$O(n^2)$	平方	氣泡排序，插入排序
$O(n^3)$	三次方	三重迴圈枚舉法，高斯消去法求解線性方程組
$O(2^n)$	指數	費氏數列
$O(n!)$	階層	排列組合，八皇后問題

O(1): Constant time

不管帶入的 n 多大，執行時間不會隨著 n 變大而增加，固為

$O(1)$。

/**
 * @param {number} n The number
 */
function printNum(n){
    console.log(n);
}

printNum(10);

O(n): Linear time

隨著輸入的增長，算法的完成時間會相應增加，取最大階項n，固為

$O(n)$。

/**
 * @param {number} n The number
 */
function forloop(n){
    for(i=0;i<n;i++){
        console.log(i);
    }
}

forloop(10);

O(log n): Logarithmic time

/**
 * @param {number} n The number
 */
function Logarithmic(n){
    let i = 1;
    while(i < n){
        i = i * 2;
    }
}
Logarithmic(8);

可以發現i會是

$$2^0,2^1,2^2,2^3,2^4,...2^n$$結果與自身反覆相乘，就表明正使用對數算法，能夠對半

$（n/2）$處理的通常都屬於

$O(logn)$ 的演算法
假設 n 是 8，迴圈總共會跑 3 次，

$n=2^3$也就是

$\log 2^n=3$ ，將底數忽略，時間複雜度為

$O(\log n)$

$O(logn)$基本上意味著時間呈線性增長，而n呈指數增長。因此，如果計算2元素需要一秒鐘，計算4元素則需要2幾秒鐘，計算8元素需要幾3秒鐘，依此類推等等。

O(n^3): Cubic time

此函式接受兩個陣列 A 和 B，並傳回它們相乘的結果。它使用三個巢狀迴圈，最外層回圈遍歷第一個陣列的列，中間層的迴圈遍歷第二個陣列的行，最內層陣列遍歷相應行和列的元素。

以下程式只是個範例，有更有效的演算法來執行矩陣乘法，例如:施特拉森演算法(Strassen)算法)。

function matrixMultiplication(A, B) {
    let result = new Array(A.length).fill(0).map(() => new Array(B[0].length).fill(0));
    for (let i = 0; i < A.length; i++) {
        for (let j = 0; j < B[0].length; j++) {
            for (let k = 0; k < A[0].length; k++) {
                result[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    return result;
}

O(2^n): Exponential time

使用循環遍歷輸入陣列的元素，對於每個元素，它透過將元素添加到每個現有子集來建立一個新子集。每添加一個元素，子集的數量就會加倍。此函式的時間複雜度為

$O(2^n)$，因為它會產生

$2^n$ 個子集，其中

$n$ 是輸入陣列的大小。

function generateSubsets(set) {
    let subsets = [[]];
    for (let i = 0; i < set.length; i++) {
        let current = set[i];
        let n = subsets.length;
        for (let j = 0; j < n; j++) {
            let subset = subsets[j].slice();
            subset.push(current);
            subsets.push(subset);
        }
    }
    return subsets;
}

generateSubsets([1, 5]) // [[], [1], [5], [1, 5]]

位元操作Bit manipulation改進

時間複雜度保持不變，但通過減少迭代次數和操作次數提高了性能。

function generateSubsetsUsingBitManipulation(set) {
    let n = set.length;
    let subsets = [];
    for (let i = 0; i < (1 << n); i++) {
        let subset = [];
        for (let j = 0; j < n; j++) {
            if (i & (1 << j)) {
                subset.push(set[j]);
            }
        }
        subsets.push(subset);
    }
    return subsets;
}

generateSubsetsUsingBitManipulation([1, 5]) // [[], [1], [5], [1, 5]]

O(n!): Factorial time

這個函式只要產生了所有的 n 階層的排列，其中 n 是輸入陣列的大小。重要的是要注意這只是一個示例，在實際情況下，有更有效的演算法來生成排列，比如 Heap 演算法。

function generatePermutations(arr) {
    let result = [];
    function permute(arr, m = []) {
        if (arr.length === 0) {
            result.push(m);
        } else {
            for (let i = 0; i < arr.length; i++) {
                let curr = arr.slice();
                let next = curr.splice(i, 1);
                permute(curr.slice(), m.concat(next))
            }
        }
    }
    permute(arr);
    return result;
}

generatePermutations([1,2]) // [[1, 2], [2, 1]]

使用Heap演算法改進

使用了Heap的演算法來產生所有的排列，相比於上一個是一種更加高效的方法。它使用遞迴函式，在每次遞迴呼叫中，它產生前 n-1 個元素的所有排列，並將最後一個元素與陣列中的前 n-1 個元素交換。它不在每個遞迴呼叫中使用切片slice或連接concat，這就是它比前一個更有效的原因。

function generatePermutationsUsingHeapsAlgorithm(arr) {
    let result = [];
    function permute(arr, n) {
        if (n === 1) {
            result.push(arr.slice());
        } else {
            for (let i = 0; i < n; i++) {
                permute(arr, n - 1);
                if (n % 2 === 0) {
                    swap(arr, i, n - 1);
                } else {
                    swap(arr, 0, n - 1);
                }
            }
        }
    }

    function swap(arr, i, j) {
        let temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    permute(arr, arr.length);
    return result;
}

generatePermutationsUsingHeapsAlgorithm([1,2]) // [[1, 2], [2, 1]]

空間複雜度

程式執行所需的記憶體空間

介紹

時間複雜度與空間複雜度是互相

也就是以時間換取空間，以空間換取時間

以下為常見空間複雜度

Big O Notation	介紹	常見
$O(1)$	不隨輸入資料量增加而增加	常數空間的演算法
$O(n)$	記憶體空間和輸入資料量等同	需要儲存輸入資料的演算法
$O(n^2)$	記憶體空間是輸入資料量的平方	需要儲存兩兩之間關係的演算法
$O(logn)$	記憶體空間輸入資料量之間呈對數關係	遞迴演算法
$O(nlogn)$	記憶體空間是輸入資料量乘以log(輸入資料量)	#
$O(n+k)$	#	基數排序
$O(2^n)$	記憶體空間是 2 的輸入資料量次方	#

$O(1)$ 空間複雜度

函式僅使用恆定數量的記憶體來儲存 sum 變數，而不管 a 和 b 的輸入值如何。因此，這個函式的空間複雜度是

$O(1)$。

function addNum(a, b) {
    let sum = a + b
    return sum;
}

addNum(4, 5) // 9

$O(n)$ 空間複雜度

範例為反轉陣列，儲存反轉陣列的大小與輸入陣列的大小成正比。因此，這個函數的空間複雜度是

$O(n)$。

function reverseArray(arr) {
    let reversedArr = [];
    for (let i = arr.length - 1; i >= 0; i--) {
        reversedArr.push(arr[i]);
    }
    return reversedArr;
}

reverseArray([5,8,7,9,10]) // [10, 9, 7, 8, 5]

$O(n^2)$ 空間複雜度

該函數使用一個陣列來儲存輸入陣列中所有可能的元素對。對數為

$n(n-1)/2$ 個，其中 n 是輸入陣列的大小。因此，這個函數的空間複雜度是

$O(n^2)$。

function generatePairs(arr) {
    let pairs = [];
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            if (i !== j) {
                pairs.push([arr[i], arr[j]]);
            }
        }
    }
    return pairs;
}

generatePairs([1,3]) // [[1, 3], [3, 1]]

$O(logn)$空間複雜度

該函數使用遞迴對輸入陣列執行二分搜尋法。
該函數僅使用少量記憶體來儲存高低指標(high, low)和中間變數(mid)，以及遞迴的呼叫的stack。 由於 stack 的大小與輸入陣列大小的對數成正比，因此該函數的空間複雜度為

$O(logn)$。

function binarySearch(arr, target) {
    function search(low, high) {
        if (low > high) {
            return -1;
        }
        let mid = Math.floor((low + high) / 2);
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            return search(mid + 1, high);
        } else {
            return search(low, mid - 1);
        }
    }
    return search(0, arr.length - 1);
}

$O(n+k)$空間複雜度

基數排序的空間複雜度通常為

$O(n+k)$，其中 n 是輸入陣列中元素的數量，k 是可能的數字或位數。這是因為基數排序使用輔助資料結構（例如計數陣列或buckets）在對元素進行排序時臨時儲存元素。

function radixSort(arr) {
    let max = Math.max(...arr);
    let maxDigits = (max + '').length;
    for (let i = 0; i < maxDigits; i++) {
        let buckets = Array.from({length: 10}, () => []);
        for (let j = 0; j < arr.length; j++) {
            let digit = getDigit(arr[j], i);
            buckets[digit].push(arr[j]);
        }
        arr = [].concat(...buckets);
    }
    return arr;
}

function getDigit(num, place) {
    return Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
}

radixSort([5,4,8,9,10]) // [4, 5, 8, 9, 10]

特別感謝

感謝Howard Gou大大訂正