空间复杂度基础

学习目标

本节学习空间复杂度。

空间复杂度描述的是算法运行过程中额外占用的内存空间如何随输入规模增长。它和时间复杂度一样，也关注增长趋势，而不是精确到每一个字节。

什么是额外空间

分析空间复杂度时，通常重点关注算法为了完成任务额外申请的空间，而不是输入数据本身已经占用的空间。

例如，一个函数接收一个数组作为输入，然后只使用几个变量完成计算。虽然数组本身占用了空间，但这部分通常不算作算法额外空间。我们更关心函数内部额外创建了多少辅助数据。

常数空间复杂度

如果算法只使用固定数量的额外变量，不管输入规模多大，额外空间都不明显增长，那么空间复杂度通常是 $O(1)$ 。

int sumNumbers(const vector<int>& numbers) {
    int sum = 0;

    for (int number : numbers) {
        sum += number;
    }

    return sum;
}

int sumNumbers(int[] numbers) {
    int sum = 0;

    for (int number : numbers) {
        sum += number;
    }

    return sum;
}

def sum_numbers(numbers):
    total = 0

    for number in numbers:
        total += number

    return total

int SumNumbers(int[] numbers)
{
    int sum = 0;

    foreach (int number in numbers)
    {
        sum += number;
    }

    return sum;
}

这段代码会遍历所有元素，所以时间复杂度是 $O(n)$ 。但它只额外使用了一个累加变量，因此额外空间复杂度是 $O(1)$ 。

线性空间复杂度

如果算法额外创建了一个与输入规模同样增长的新集合，那么空间复杂度通常是 $O(n)$ 。

例如，复制数组或列表：

vector<int> copyNumbers(const vector<int>& numbers) {
    vector<int> copied;

    for (int number : numbers) {
        copied.push_back(number);
    }

    return copied;
}

int[] copyNumbers(int[] numbers) {
    int[] copied = new int[numbers.length];

    for (int i = 0; i < numbers.length; i++) {
        copied[i] = numbers[i];
    }

    return copied;
}

def copy_numbers(numbers):
    copied = []

    for number in numbers:
        copied.append(number)

    return copied

int[] CopyNumbers(int[] numbers)
{
    int[] copied = new int[numbers.Length];

    for (int i = 0; i < numbers.Length; i++)
    {
        copied[i] = numbers[i];
    }

    return copied;
}

这里新集合 copied 的长度会随着输入长度增长，所以额外空间复杂度是 $O(n)$ 。

时间与空间的取舍

很多数据结构设计都涉及时间和空间的取舍。

哈希表是典型例子。它通常会使用额外空间维护键和值之间的映射关系，从而换取更快的查找速度。也就是说，我们愿意多占用一些内存，让查找操作更高效。

相反，如果内存非常有限，可能就不能随意创建大型辅助结构，需要接受更慢的处理方式。

这类权衡会在后续章节中反复出现。

递归也会占用空间

递归调用会使用调用栈空间。即使代码中没有显式创建新数组，递归深度也可能带来额外空间成本。

例如，一个递归函数如果每次只把问题规模减少 1，递归深度可能达到 $n$ ，调用栈空间就可能是 $O(n)$ 。

这也是分析空间复杂度时容易忽略的地方。

本节小结

空间复杂度描述算法额外内存消耗随输入规模增长的趋势。

只使用固定变量通常是 $O(1)$ ，额外创建与输入规模相同的新集合通常是 $O(n)$ 。学习数据结构时，要同时关注时间效率和空间代价，因为很多高效方案本质上都是在二者之间做取舍。