考点4　空间复杂度

例．某算法的空间复杂度为O(1)，则（　　）。【2015年四川大学】

A．该算法执行不需要任何辅助存储空间

B．该算法执行所需辅助存储空间的大小与问题规模n无关

C．该算法执行不需要任何存储空间

D．该算法执行所需存储空间的大小与问题规模n无关

【答案】 B

【解析】本题考查空间复杂度的分析。空间复杂度与时间复杂度相似，它们都是数学上的渐进表示方式。空间复杂度的意义为在算法执行过程中，不需要大于常数级别的辅助存储空间，而不是不需要大于常数级别的存储空间。这里考生应清楚存储空间与辅助存储空间的易混淆之处。

误区警示

空间复杂度描述的是算法执行期间所需辅助存储空间的大小。它通常以数据结构的存储空间和程序使用空间的度量来评估算法的空间性能。