GESP 八级 · GESP 202503 C++ 八级 第 8 题

下列关于算法的说法，错误的是（ ）。

逐项分析每个选项，利用C++语法规则和算法知识判断正误。注意隐含条件（如整型溢出、栈溢出）。

注意题目问的是"错误的是"还是"正确的是"，避免看反。选项中若有绝对化表述通常错误。

【考点】枚举法｜贪心算法｜分治算法｜倍增法

A 选项陈述的是枚举法的本质属性，算法竞赛中常考"暴力枚举"的边界问题。枚举法确实能解决一切有限问题——只要给定范围，穷举所有可能并验证即可，这是算法定义层面的真理，命题人用"足够时间空间"做限定，恰恰是承认了枚举的完备性而非局限性。

B 选项存在致命概念偷换。分治算法的三个核心要求是：1) 将原问题分解为规模更小的子问题 2) 递归求解各子问题 3) 合并子问题结果。关键陷阱在于"子问题必须相互独立"——这是错误的。典型反例：归并排序中，[1,3,5,7] 分解为 [1,3] 和 [5,7] 两个子问题，它们共享原数组的存储结构；更隐蔽的是"最大连续子数组和"问题，分治时左右子问题常有重叠计算。命题人故意把"可分解"伪装成"必须独立"，考察考生对分治本质的理解。

C 选项描述的是贪心算法相对于暴力法的优势，正确。贪心策略（如活动选择问题中的"最早结束优先"）能避免回溯，时间复杂度从指数级降到线性对数级。

D 选项讲的是倍增法（Binary Exponentiation）的变体应用，正确。倍增法核心是通过步长指数增长快速逼近：在搜索未知长度有序数组时，先 1→2→4→8 跳跃定位区间，再反向减半收缩范围，类似"指数探测+二分收缩"的经典套路。

【陷阱拆解】B 选项的"必须相互独立"是绝对化表述，分治算法的子问题天然存在依赖关系——它们共享原问题的输入输出空间，且合并步骤需要左右子结果交互。考生若死记"分治=独立子问题"，就会掉进这个语义陷阱。真正考点在于：分治的"分"是规模分解，不是逻辑独立。

【反命题思维】若把 B 改为"分治算法分解出的子问题规模必须严格减半"，答案就变了——二分搜索分解为 [0, n/2) 和 [n/2, n)，规模约等于减半，但二分归并排序中左右子问题规模是相等的，并非"减半"。命题人改条件就能让答案从 B 变成另一个陷阱。刷到分治相关题时，先问自己：题目说的是"分解规模"还是"子问题独立性"？这是两个不同维度的概念。