大 O 表示法：空间复杂度

Java 代码优化

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

什么是空间复杂度？

时间复杂度描述输入规模如何影响运行时间
空间复杂度描述输入规模如何影响内存占用

理解空间复杂度有助于构建以下应用：

只用必要的内存，不多占
避免如 OutOfMemoryError 的崩溃

大 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 个还是 1000 万个元素，只需为一个变量 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. 时间复杂度

请记住：

有时用空间换时间
有时用时间换空间
取舍取决于具体约束

图示时间与空间的权衡

Passons à la pratique !

Java 代码优化