北京海淀区信息学竞赛 · 2024 北京市海淀区信息学竞赛（初赛）试题 第 4 题

下列有关提高穷举算法效率的方法中，说法错误的是（ ）

这题考穷举算法优化，别被选项C的'函数分解'迷惑，直接对比各选项原理，找那个'看起来合理实则无效'的坑。

学生容易把'函数分解'理解为优化手段，其实分解只是把大问题拆小，若子问题仍需穷举，总复杂度未必降低；更常见的错是把预处理、空间换时间当成万能药，忽略了它们适用的前提条件。

这道题考查穷举算法的效率优化思路，核心在于理解哪些手段能真正减少计算量或判断次数，而不是单纯改变代码结构。

先拆解四个选项背后的原理：A项'推导减少范围'是穷举的精髓，比如求素数时不必遍历到n，只需到√n，这是通过数学性质直接剪枝；B项'预处理避免重复计算'也很常见，像杨辉三角用二维数组存结果，后续直接查表，不再重复递推；D项'空间换时间'是经典策略，比如用哈希表记录已访问状态，避免重复判断，虽然占用内存但减少了逻辑判断的开销。

C项'用更小规模的函数分解现有函数'听起来很专业，但这里有个陷阱：分解函数本身不改变穷举的本质。若原函数是用穷举解决子问题，分解后子问题规模变小了，但子问题依然要穷举，总复杂度往往还是由最慢的那个子问题决定。除非分解后能引入新的数学性质或剪枝策略，否则单纯分解并不能提高穷举效率。命题人就是在这里挖坑，让不熟悉算法复杂度分析的同学误以为'分解=优化'。

思考时先问自己：这个操作能否减少需要尝试的候选数量？能否避免重复计算？能否用空间换时间？C项显然不满足这些条件，它只是改变了代码的调用结构，没有触及穷举的核心瓶颈。

考频趋势方面，穷举算法优化是信息学竞赛高频考点，近五年在CSP-J/S和NOIP中几乎每年都有涉及，尤其是结合数论、组合数学的剪枝技巧。未来命题仍会侧重'数学推导优化穷举范围'和'预处理/空间换时间'的组合应用，C项这种'伪优化'的干扰项大概率会继续出现，用来测试学生对算法本质是否真正理解。