NOIP 提高组初赛 · NOIP 2011 提高组初赛试题 第 6 题

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

这题考的是算法分析里最基础也最容易混淆的概念——空间复杂度到底‘算’什么。拿到题别急着背定义，先想：空间复杂度是评价算法效率的，那它肯定只关心程序跑起来那一刻的开销，跟程序存在硬盘里多大、写了多少行代码完全没关系。所以第一步就要把‘运行时的内存’和‘静止时的硬盘’区分开，答案自然就指向A了。

学生最容易掉进‘数组’这个坑里，觉得空间复杂度就是看用了几个数组，其实数组只是内存里的一部分，根本没涵盖栈帧、临时变量这些开销。更常见的误区是死抠字眼，看到‘空间’就联想到‘硬盘’，觉得C或D也对，甚至觉得源文件大说明算法复杂（D选项），这都是把‘程序文件’和‘程序运行’混为一谈。命题人就是爱在这种概念边界上挖坑，让你以为多选其实单选，让你觉得硬盘也是‘空间’其实不是。记住，空间复杂度只盯着内存，硬盘和源文件统统不在考虑范围内。

考点与概念人话版

空间复杂度，说白了就是算法跑起来时，临时占用的内存有多大。这个‘内存’是个统称，包含两部分：一是输入数据本身占的地方，二是算法过程中为了计算临时开辟的辅助变量、递归栈帧等占的地方。它是个‘动态’指标，只看程序执行那一瞬间的内存足迹。

命题人怎么挖坑

这道题的陷阱就在‘空间’这个词上。命题人故意把‘内存’和‘硬盘’混在一起，让你以为所有存储介质都算。实际上，空间复杂度只关心内存，硬盘是持久化存储，跟算法效率分析无关。源文件大小更是静态属性，跟算法跑起来占多少内存完全没关系。数组只是内存的一部分，不能代表全部，所以B也是错。

思考心法：拿到题怎么推

1. 先锁定核心词：‘空间复杂度’。 2. 回忆定义：算法运行时的内存占用。 3. 拆解‘内存’：包括输入 + 辅助变量。 4. 排除干扰项：硬盘、源文件、部分内存（如仅数组）都不符合定义。 5. 直接对应选项：A是‘运行时理论上所占的内存空间’，完美匹配。

计算与结论

既然定义明确指向运行时内存，那么答案只能是A。B项‘数组空间’范围太窄，C项‘硬盘空间’和D项‘源文件大小’完全偏离主题，都是命题人设的坑。

避坑提醒

千万别被‘空间’二字误导，以为硬盘也算。空间复杂度是算法分析里的‘运行时’指标，不是‘存储’指标。记住这个区别，以后遇到类似题目就不会再纠结了。

考频与趋势

从真实数据看，‘计算机发展史’相关题目在NOIP初赛里出现频率很高：题库共考过29题，覆盖3个级别（2007-2020）。逐年分布：2007年5题、2008年6题、2009年2题、2010年2题、2011年3题、2012年9题、2013年1题、2020年1题。分赛事来看，NOIP提高组初赛15题、NOIP普及组初赛13题、CSP提高级1题。这说明这类基础概念题在NOIP初赛里是常客，尤其是提高组。

预测

基于数据，未来NOIP提高组初赛仍大概率会考这类基础概念辨析题，形式可能继续以单选题为主，偶尔出现填空题或简答题，但核心考点不会变：区分‘运行时内存’与‘静止时硬盘’。暂无足够依据预测具体年份或题型变化，但考生应重点巩固此类概念辨析能力。