什么是分治法
答案要点
- 三步:分解、解决、合并,规模足够小时直接求解
- 子问题结构相同且相互独立
- 典型应用:归并排序、快速排序、二分查找、最近点对
- 复杂度用递推式和主定理分析,如 T(n)=2T(n/2)+O(n) 得 O(n log n)
- 与动态规划区别:DP 子问题重叠,需要记忆化
易错点
- 把子问题重叠的问题硬用分治,导致指数级重复计算
- 忘记写递归出口
- 以为分治一定比直接解法快,忽略合并开销
面试官常见追问
- 归并排序和快速排序在分治上有什么不同?
- 主定理怎么用?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。