Space-Complexity

定义 Definition

空间复杂度：衡量一个算法在运行过程中所需的额外内存空间随输入规模 \(n\) 增长而变化的数量级，通常用大 \(O\) 表示（如 \(O(1)\)、\(O(n)\)、\(O(n^2)\)）。除常见情形外，有时也会区分是否把输入本身占用的空间计入。

例句 Examples

The space-complexity of this algorithm is O(1).
这个算法的空间复杂度是 O(1)。

Although the method reduces time, its space-complexity grows to O(n), which can be a problem for very large datasets.
虽然这种方法减少了时间开销，但它的空间复杂度增长到 O(n)，对超大数据集可能会造成问题。

发音 Pronunciation

/spes kmplksti/

词源 Etymology

space（空间、内存）+ complexity（复杂度）。该术语源自计算机科学对算法资源消耗的分析传统，与“时间复杂度（time complexity）”并列，用来描述算法对内存资源的需求随输入规模变化的趋势。“complexity”来自拉丁语 complexus（交织的、复杂的），在现代语境中引申为“复杂程度/量级”。

相关词 Related Words

• Time Complexity
• Big O Notation
• Auxiliary Space
• Memory Usage
• Asymptotic Analysis
• Algorithm
• Data Structure
• Recursion Stack

文学与经典著作中的用例 Literary Works

• 《Introduction to Algorithms》（CLRS）：在渐进分析章节中系统讨论时间与空间复杂度，并以排序、动态规划等算法为例对比空间开销。
• Donald E. Knuth《The Art of Computer Programming》：在算法分析与实现细节讨论中经常涉及空间需求与存储成本。
• Aho, Hopcroft, Ullman《The Design and Analysis of Computer Algorithms》：以理论分析方式对算法的时间/空间资源界限进行说明。
• Steven S. Skiena《The Algorithm Design Manual》：在工程化算法选择中反复强调“用空间换时间/用时间换空间”的权衡。