NOIP 普及组初赛 · NOIP 2011 普及组初赛试题 第 12 题

在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（ ）。

这题考的是‘空间复杂度’的定义。拿到题先想：算法分析里‘空间’到底指哪块资源？时间复杂度盯CPU，空间复杂度盯内存。命题人爱把‘运行时内存’和‘硬盘/源文件’混在一起挖坑，让你选‘理论上所占的内存空间’。

很多学生会把‘空间’理解成程序占用的所有地方，比如硬盘上的源文件、编译后的可执行文件，或者只想到数组这种显式数据结构。其实空间复杂度只统计算法运行过程中动态或静态占用的内存（变量、栈帧、动态分配的对象等），硬盘和源文件都不算在内。

这道题考什么

题目标注‘空间复杂度’，核心就是考查你对算法资源分析中‘空间’这一概念的理解：它究竟指代程序运行时占用的哪一部分资源。

概念讲人话

空间复杂度，简单来说，就是衡量一个算法在程序运行过程中理论上需要占用多少内存空间。

这里的‘内存’，指的是计算机内存条里的那块区域（RAM）。算法执行时，变量存储、数组存放、递归调用产生的栈帧、动态申请的对象，统统都要往内存里写。所以，空间复杂度就是把这些占用的内存总量抽象成一个关于输入规模n的函数，比如 O(n) 或 O(log n)。