NOIP 提高组初赛 · NOIP 2012 提高组初赛试题 第 11 题

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

这题考大O表示法的核心定义：常数倍不影响阶。拿到题先别急着算，把选项都化成 2 的幂次看底数，只要底数还是 2，前面乘个常数（哪怕是个变量 n）都不出 O(2^n) 的量级，直接锁定 A。

最容易栽跟头的就是死记硬背“指数必须完全一样”，看到 2^(n+1) 就以为是 O(2^(n+1)) 而不敢选，或者被 D 项 2^(2n) 唬住以为它和 2^n 差不多。其实命题人就是爱在指数上玩加减乘，考你懂不懂“常数倍”和“变量倍”的区别。B 项 3^n 和 C 项 n×2^n 都是典型的干扰项，前者底数大了，后者多了个 n，都直接跳出 O(2^n) 的范围，但学生容易因为 C 项里也有 2^n 就犹豫，得提醒他们 n 是变量，不是常数，一乘就变阶了。

考点直击：这道题考查的是大 O 记号中“常数倍”与“变量倍”的本质区别。命题人故意把正确答案藏在指数变形里，而把错误答案设计成底数变大或多乘一个 n，专门挖那些只背公式不真懂定义的坑。

概念大白话：O(2^n) 的意思是，运算次数最多是某个常数 c 乘以 2^n。注意，这个 c 必须是常数，不能带 n。只要底数还是 2，前面乘个常数（哪怕是个变量 n）都不出 O(2^n) 的量级；一旦底数变了，或者前面多了个 n，那就直接越界了。

逐项拆解：

• A. 2^(n+1)：展开就是 2 × 2^n。前面的 2 是常数，完全符合 O(2^n) 定义，正确。
• B. 3^n：底数从 2 变成了 3，增长速度远超 2^n，显然不是 O(2^n)。
• C. n × 2^n：这里有个 n，n 是变量，不是常数。虽然它包含 2^n，但多乘了个 n 后，阶数变成了 O(n·2^n)，已经超出了 O(2^n) 的范围。
• D. 2^(2n)：展开就是 4^n，底数变成了 4，和 2^n 完全是两个量级。

思考心法：遇到这种题，别被指数吓住，先把选项化成 2 的幂次看底数。只要底数还是 2，前面乘个常数（哪怕是个变量 n）都不出 O(2^n) 的量级，直接锁定 A。

避坑提醒：最容易栽跟头的就是死记硬背“指数必须完全一样”，看到 2^(n+1) 就以为是 O(2^(n+1)) 而不敢选，或者被 D 项 2^(2n) 唬住以为它和 2^n 差不多。其实命题人就是爱在指数上玩加减乘，考你懂不懂“常数倍”和“变量倍”的区别。B 项 3^n 和 C 项 n×2^n 都是典型的干扰项，前者底数大了，后者多了个 n，都直接跳出 O(2^n) 的范围，但学生容易因为 C 项里也有 2^n 就犹豫，得提醒他们 n 是变量，不是常数，一乘就变阶了。

考频与趋势：计算机发展史是历年常客，从 2007 到 2020 年共考过 29 题，覆盖 NOIP 提高组、普及组及 CSP 提高级。其中 2012 年 NOIP 提高组初赛一口气考了 9 题，是历年单年最高峰，说明这类基础概念题在提高组初赛里确实高频出现。2008 年也有 6 题，2007 年 5 题，整体分布较均匀，但 2012 年那次爆发值得注意。

未来预测：基于现有数据，计算机发展史在 NOIP 提高组初赛的考频依然较高，未来几年大概率会继续作为送分题出现，形式可能仍是这种概念辨析或简单计算。暂无足够依据预测具体年份或题型变化。