NOIP 提高 2012 第一轮 第 11 题：如果对于所有规模为 n 的输入，一个算法均恰好进行（ ）次运算，我们可以说该算法

题目

如果对于所有规模为 $n$ 的输入，一个算法均恰好进行（	）次运算，我们可以说该算法的时间复杂度为 $O(2^n)$。

答案

A

题解

考点定位

本题考「大 O 记号理解（不定项）」,对应大纲 4.1.1 复杂度（难度【2】）。

解题过程

恰好 T(n) 次运算时 T(n)=O(2ⁿ) 需 T(n) ≤ c·2ⁿ。检验：

• 2^{n+1} = 2·2ⁿ ≤ 2·2ⁿ ✓（A）；
• 3ⁿ > c·2ⁿ 对任意常数 c（比值 (3/2)ⁿ→∞）✗；
• n×2ⁿ > c·2ⁿ（n→∞）✗；
• 2^{2n} = 4ⁿ ✗。

答案：A。

易错提醒

① 大 O 的严格定义：存在常数 c 与 n₀；② 「恰好 n×2ⁿ 次运算」的算法是 Θ(n·2ⁿ)，不是 O(2ⁿ)。