GESP 五级 · GESP 202506 C++ 五级第 23 题

判断题 · 答案 B · 考点：分治算法、算法

题目

分治算法将原问题可以分解成规模更小的子问题，使得求解问题的难度降低。但由于分治算法需要将问题进行分解，并且需要将多个子问题的解合并为原问题的解，所以分治算法的效率通常比直接求解原问题的效率低。

答案：B

分治算法算法

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

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

【考点】分治算法｜算法效率分析｜递归子问题

五级《算法与数据结构》模块，核心考点是分治算法的效率特性。命题人卡住的是考生对"分治"二字的片面理解——看到"分解"就联想到额外开销，看到"合并"就联想到时间浪费，完全忽略了分治的核心优势在于将难以直接求解的复杂问题转化为多个简单子问题。

第 28 题· NOIP 2007 普及组初赛试题 · 答案 return(dr<tr+s)&&(dc<tc+s)dr<tr+s&&dc<tc+schessboard(tr,tc,tr+s-1,tc+s-1,s)chessboard(tr,tc+s,tr+s-1,tc+s,s)chessboard(tr+s,tc,tr+s,tc+s-1,s)chessboard(tr+s,tc+s,tr+s,tc+s,s)看解析 →
第 27 题· NOIP 2008 提高组初赛试题 · 答案 a[left];a[j]<valuea[j]<=valuea[i]>valuea[i]>=valuea[i] = value; i + 1,right,n FindKth(left, i – 1, n);看解析 →
第 26 题· NOIP 2009 普及组初赛试题 · 答案 NPOI看解析 →
第 28 题· NOIP 2011 提高组初赛试题 · 答案 num++num = num + 1j = isolve(left, j - 1, deep + 1)solve(j + 1, right, deep + 1)看解析 →
第 15 题· NOIP 2012 普及组初赛试题 · 答案 C看解析 →

在 OI伴学里做这道题

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