数据结构基础题：空间复杂度 O(1) 到底表示什么？

题目

若某算法的空间复杂度为 O(1)，则表示该算法（ ）。

A. 不需要任何辅助空间

B. 所需辅助空间大小与问题规模 n 无关

C. 不需要任何空间

D. 所需空间大小与问题规模 n 无关

答案速览

正确答案：B. 所需辅助空间大小与问题规模 n 无关

空间复杂度为 O(1)，表示算法运行过程中使用的额外辅助空间是常量级的，不会随着问题规模 n 的增大而增大。

详细解析

1. 空间复杂度看什么？

空间复杂度通常用来衡量算法在运行过程中额外需要的存储空间，常记为：

S(n)=O(g(n))

其中 n 表示问题规模，S(n) 表示算法额外空间消耗随 n 的变化趋势。

在数据结构和算法分析中，空间复杂度通常重点关注：

• 临时变量；
• 辅助数组；
• 递归调用栈；
• 临时表、队列、栈等辅助结构。

而输入数据本身一般属于问题给定的数据，不是算法额外开辟的辅助空间。

2. O(1) 表示“常量级空间”

如果一个算法的空间复杂度是 O(1)，说明它额外使用的空间数量是固定的。

也就是说：

不管 n 是 10、1000，还是 100000，算法额外使用的辅助空间数量都大致不变。

例如：

int sum = 0;
for (int i = 0; i < n; i++) {
    sum += A[i];
}

这段代码虽然遍历了长度为 n 的数组，但额外只用了 sum 和 i 这类固定数量的变量，因此空间复杂度是：

O(1)

为什么不是 A？

A 选项说：不需要任何辅助空间。

这说得太绝对了。

O(1) 并不表示完全不使用辅助空间，而是表示使用的辅助空间是常量级。例如使用 1 个变量、2 个变量、5 个变量，只要数量不随 n 增长，都属于 O(1)。

所以 A 错在“任何”两个字。

为什么不是 C？

C 选项说：不需要任何空间。

这更不正确。任何算法运行都需要空间，例如：

• 程序指令需要空间；
• 变量需要空间；
• 输入数据也要占空间；
• 函数调用也可能占空间。

空间复杂度 O(1) 绝不是“不占空间”。

为什么不是 D？

D 选项说：所需空间大小与问题规模 n 无关。

这个说法容易误导，因为“所需空间”可能包括输入数据本身。如果输入数组长度为 n，那么输入数据本身占用的空间显然和 n 有关。

算法分析中通常说空间复杂度时，更准确的表达是：

算法所需的辅助空间大小与问题规模 n 无关。

所以 B 比 D 更准确。

四个选项对比

举例理解

O(1)：固定辅助空间

int max = A[0];
for (int i = 1; i < n; i++) {
    if (A[i] > max) {
        max = A[i];
    }
}

这段代码只额外使用 max 和 i 两个变量，变量数量不随 n 增长，因此空间复杂度是 O(1)。

O(n)：辅助空间随 n 增长

int B[n];
for (int i = 0; i < n; i++) {
    B[i] = A[i];
}

这里额外创建了长度为 n 的数组 B，辅助空间随 n 增长，因此空间复杂度是 O(n)。

一句话记忆

O(1) 不是“不用空间”，而是“额外辅助空间固定不变”。

自测题

如果一个算法只额外使用了 3 个整型变量和 1 个临时指针，那么它的空间复杂度是多少？