NOIP 提高 2012 第一轮 第 20 题：以下关于计算复杂度的说法中，正确的有（

题目

以下关于计算复杂度的说法中，正确的有（   ）。

答案

B、D

题解

考点定位

本题考「复杂度类论述（不定项）」,对应大纲 4.1.1 复杂度（难度【4】）。

解题过程

按选项表述（A/C 为同一命题的两种：无多项式时间算法的陈述；B/D 为空间版本）：

• 时间维度：不存在多项式时间算法 ⇏ 不存在指数时间算法等——正确的表述是「不存在多项式时间算法的问题，仍然可能存在指数时间算法」→ B ✓；
• 空间维度：D ✓。

（A/C 的「那它一定是…」绝对化表述错误。）

答案：B、D。

易错提醒

① 无多项式时间解 ≠ 无任何解（指数/阶乘算法也算解）；② 绝对化措辞「一定」「必然」在复杂度论述题中多为错误选项。