Big-O 表示法：空間複雜度

Java 程式碼最佳化

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

什麼是空間複雜度？

時間複雜度描述輸入大小如何影響執行時間
空間複雜度描述輸入大小如何影響記憶體用量

理解空間複雜度很重要，才能打造：

只用到剛好的記憶體，不多占
避免發生如 OutOfMemoryError 的當機錯誤

Big-O 表示法

表示法與時間複雜度相同。

常見複雜度類別：

O(1)：常數等級——與大小無關
O(n)：線性等級——隨輸入成長
O(n²)：平方等級——隨輸入平方成長

尋找最大值的方法

public int findMax(int[] array) {
    int max = Integer.MIN_VALUE;
    for (int value : array) {
        if (value > max) {
            max = value;
        }
    }
    return max;
}

不論整數陣列有 10 個或 1,000 萬個元素，我們只需為單一變數 max 配置記憶體
空間複雜度是 O(1)，也就是常數空間

倍增陣列的方法

public int[] doubleValues(int[] array) {
    int[] result = new int[array.length];
    for (int i = 0; i < array.length; i++) {
        result[i] = array[i] * 2;
    }
    return result;
}

若輸入有 n 個元素，就需要為 n 個額外元素配置空間
空間複雜度為 O(n)，因為額外記憶體隨輸入大小線性成長

乘法表的方法

public int[][] multiplicationTable(int n) {
    int[][] table = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            table[i][j] = (i + 1) * (j + 1);
        }
    }
    return table;
}

若 n 是 10，需要 100 個儲存格；若 n 是 100，需要 10,000 個儲存格
我們將其歸類為 O(n²)

為何空間複雜度重要？

記憶體是有限資源！

上述範例在輸入大小為 10,000 時的情況：

findMax，O(1) -> 只需多幾個位元組
doubleValues，O(n) -> 約 40KB 額外記憶體
multiplicationTable，O(n²) -> 約 400MB 額外記憶體

長條圖顯示 findMax 增加 8 位元組、doubleValues 增加 40KB、multiplicationTable 增加 400MB 的記憶體用量

空間 vs. 時間複雜度

別忘了：

有時以空間換時間
有時以時間換空間
正確取捨取決於你的限制條件

象徵時間與空間權衡的圖像

一起來練習吧！

Java 程式碼最佳化