Space Complexity

Definition / 定义

Space complexity（空间复杂度）：在算法运行过程中，为完成计算所需要的额外内存空间随输入规模增长而变化的度量，通常用大 O 表示法（如 O(1), O(n), O(n log n)）。它常关注辅助空间（临时数组、递归栈、哈希表等），有时也会讨论包含输入本身的“总空间”。（该术语在计算机科学中是复杂度分析的核心概念之一。）

Pronunciation / 发音

/ˈspeɪs kəmˈplɛksəti/

Examples / 例句

This algorithm has O(n) space complexity because it stores an extra array of size n.
这个算法的空间复杂度是 **O(n)**，因为它存储了一个大小为 n 的额外数组。

Although the time complexity is fast, the space complexity becomes a problem when the dataset is too large to fit in memory.
尽管时间复杂度很快，但当数据集大到无法装入内存时，空间复杂度就会成为问题。

Etymology / 词源

space 源自拉丁语 spatium，意为“空间、距离”；complexity 源自拉丁语 complexus（“交织在一起的”），引申为“复杂程度”。在算法分析语境中，“space complexity”字面义即“对所需空间增长程度的度量”，与 “time complexity（时间复杂度）”并列，用于描述资源消耗随输入规模的变化。

Related Words / 相关词

• Auxiliary
• Memory
• Big-O
• Complexity
• Time
• Recursion
• Stack
• Heap
• Trade-off

Literary Works / 文学作品

• Introduction to Algorithms（《算法导论》）——在算法分析章节中系统讨论时间与空间复杂度。
• The Art of Computer Programming（《计算机程序设计艺术》）——涉及算法效率分析，包含对空间使用的严谨讨论。
• Algorithm Design（《算法设计》, Kleinberg & Tardos）——在设计与分析算法时多次使用空间复杂度作为评价指标。
• The Algorithm Design Manual（《算法设计手册》, Skiena）——以工程视角强调时间/空间权衡与内存开销分析。