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

选择题 · 答案 A · 考点：贪心算法、动态规划、复杂度分析

题目

以下关于贪心法和动态规划的说法中，错误的是（）。

答案：A

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】贪心算法｜动态规划｜复杂度分析｜递推与递归实现

本题考查贪心算法与动态规划的本质区别（GESP 八级《算法设计与分析》模块核心考点）。命题人专门设置这道概念辨析题，就是要刺破考生"只背结论、不懂原理"的浅层记忆——绝大多数八级考生能背出"贪心要局部最优"，但遇到"贪心是否总能解决多阶段决策"这种需要辨析边界条件的命题，就露馅了。

第 28 题· NOIP 2010 普及组初赛试题 · 答案 num <= 2num < 3num == 2go(LEFT_TO_RIGHT)pos[i] == LEFTLEFT == pos[i]hour[i] + go(RIGHT_TO_LEFT)go(RIGHT_TO_LEFT) + hour[i]pos[i] = LEFT看解析 →
第 28 题· NOIP 2016 普及组初赛试题 · 答案 n-nn+1M[i]<C[j]M[i]<=C[j]count<=Acheck(mid)mid-1看解析 →
第 11 题· CSP 2019 入门级第一轮 · 答案 C看解析 →
第 13 题· CSP 2019 提高级第一轮 · 答案 B看解析 →
第 19 题· CSP 2019 提高级第一轮 · 答案 CDB看解析 →

在 OI伴学里做这道题

登录后可计时作答、查看完整六段式解析，并按你的错题自动生成同类练习。