空间复杂度分析 | Baeldung中文网

1. 简介

空间复杂度（Space Complexity）用于衡量一个算法或操作在运行过程中所需的总内存空间，通常与输入规模成正比。

在本文中，我们将学习如何量化空间复杂度，并通过一些 Java 示例来分析算法的内存占用情况。

最后，我们还会讨论空间复杂度与时间复杂度之间的权衡关系。

2. 常见复杂度表示法

描述空间复杂度最常用的方式是使用渐进符号（Asymptotic Notation）。其中最常用的是 Big-O 表示法，我们也会简要介绍其他几种常见表示方式。

2.1 Big-O 表示法

Big-O 表示法用于描述一个算法的渐进上界，它代表算法在最坏情况下的空间增长趋势。

✅ 通俗理解：算法所需的空间不会比某个函数 f(n) 增长得更快。

以下是一些常见的空间复杂度，按增长速度从慢到快排列：

O(1) – 常数复杂度，所需空间与输入规模无关
O(log n) – 对数复杂度，空间随输入规模的对数增长
O(n) – 线性复杂度，空间随输入规模线性增长
O(n log n) – 线性对数复杂度
O(n²) – 平方复杂度，空间随输入规模平方增长

2.2 Omega 表示法 – Ω

Omega 表示法描述的是渐进下界，即算法在最佳情况下的空间占用。

❌ 不常用：虽然 Omega 可以描述“最低内存需求”，但实际意义有限。比如我们可以说“某人至少有 10 元”，但这显然远远不够准确。

2.3 Theta 表示法 – θ

Theta 表示法用于描述一个函数的上下界，即算法的空间占用介于两个函数之间。

✅ 适用场景：当你确切知道算法的空间占用上限和下限，且两者在同一数量级时使用。

3. 空间复杂度分析实践

分析空间复杂度是评估算法效率的重要手段。本节我们通过几个 Java 示例来具体分析。

⚠️ 注意：空间复杂度受编程语言、编译器、运行环境等影响较大。我们使用 Java 举例，但可以轻松移植到其他语言，只需替换数据类型并调整内存大小即可。

3.1 常数空间复杂度 O(1)

public int sum(int a, int b) {
    return a + b;
}

该方法中使用了 3 个 int 类型变量（a、b、返回值），每个 int 占 4 字节，共 12 字节。

✅ 结论：无论输入如何变化，空间占用恒定，所以空间复杂度为 **O(1)**。

3.2 线性空间复杂度 O(n)

public int sumArray(int[] array) {
    int size = array.length;
    int sum = 0;

    for (int iterator = 0; iterator < size; iterator++) {
        sum += array[iterator];
    }

    return sum;
}

变量分析如下：

array：长度为 n，占用 4n 字节
size、sum、iterator：各占 4 字节

✅ 总空间：4n + 12 字节 → 最高次项为 n → 空间复杂度为 **O(n)**。

4. 空间与时间复杂度的权衡

在算法设计中，时间和空间往往是“鱼与熊掌不可兼得”的关系。

✅ 经典案例：

算法	时间复杂度	空间复杂度	特点
归并排序（Merge Sort）	O(n log n)	O(n)	快但占内存
冒泡排序（Bubble Sort）	O(n²)	O(1)	慢但省内存
堆排序（Heap Sort）	O(n log n)	O(1)	平衡型选手

4.1 实战：使用缓存优化时间复杂度

问题：计算斐波那契数列（递归实现）

public int fibo(int n) {
    System.out.println("Calling fibonacci with input: " + n);

    if (n < 2) {
        return n;
    }

    return fibo(n - 1) + fibo(n - 2); 
}

时间复杂度：O(2ⁿ)
空间复杂度：O(n)（递归栈）

优化思路：使用 memoization 缓存中间结果

private Map<Integer, Integer> cacheTable = new HashMap<>();

public int fibo(int n) {
    if (n < 2) {
        return n;
    }

    if (this.cacheTable.containsKey(n)) {
        return this.cacheTable.get(n);
    }

    int fiboNumber = fibo(n - 1) + fibo(n - 2);
    this.cacheTable.put(n, fiboNumber);

    return fiboNumber;
}

✅ 时间复杂度优化到 O(n)
❌ 空间复杂度增加（HashMap 占用额外内存）

4.2 如何选择？

场景	建议
内存受限	优先优化空间复杂度
CPU 资源紧张	优先优化时间复杂度
资源充足	可考虑平衡两者

⚠️ 踩坑提醒：不要盲目追求时间或空间最优。要根据实际部署环境和资源限制做取舍。

5. 总结

本文我们介绍了：

空间复杂度的基本概念
常用的表示法（Big-O、Ω、θ）
Java 示例分析不同复杂度
时间与空间的权衡关系

✅ 关键结论：

空间复杂度衡量的是算法运行时所需的内存空间
通常与输入规模成正比
时间和空间往往是互相制约的，无法同时达到最优
实际开发中要根据具体场景做权衡选择

Persistence

REST

Security