分治算法
此前学习的递归设计方法,是针对规模大的问题拆成规模小的问题,并且规模大的问题和规模小的问题的解决办法相同。
分治算法与递归设计方法的不同之处就是,该规模较大的问题分解为多个不重叠的子问题,并将其称为“分而治之”
分治的三个步骤:
- 分解:将原问题分解
- 若干个规模较小、互相不重叠与与原问题形式相同的子问题
- 合并:将各个子问题的解个并未原问题的解
- 若子问题规模较小且易于解决时候直接解出
- 否则递归地解决各个子问题
归并排序例子
问题分析
- 分解
- 将原数组分解为左右两个数组
- 分解至每个数组都只有一个元素
- 合并将两个有序数组合并为一个有序数组
- 合并算法则是比较两个数组的第一个元素大小,然后推到result数组中。
- 递归:如果数组都有多个元素,则重复上一个步骤
评论区