没有合适的资源?快使用搜索试试~ 我知道了~
gonwalk#go-algorithms#分治算法1
需积分: 0 0 下载量 142 浏览量
2022-07-25
14:28:07
上传
评论
收藏 6KB MD 举报
温馨提示
试读
1、一定是先找到最小问题规模时的求解方法 2、然后考虑随着问题规模增大时的求解方法 3、找到求解的递归函数式后(各种规模或因子),设计递归程序即可
资源推荐
资源详情
资源评论
# 分治算法思想
分治,一般使用典型的递归结构去实现。
## 分治解决问题步骤
分治算法三步走:分解 -> 解决 -> 合并
```
(1)分解原问题为结构相同的子问题。
(2)分解到某个容易求解的边界之后,进行递归求解。
(3)将子问题的解合并成原问题的解。
```
# 基本概念
在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即转化为子问题的解的合并。这个技巧是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)……
```
任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小,越容易直接求解,解题所需的计算时间也越少。例如,对于n个元素的排序问题,当n=1时,不需任何操作。n=2时,只要作一次比较即可排好序。n=3时只要作3次比较即可,…。而当n较大时,问题就不那么容易处理了。要想直接解决一个规模较大的问题,有时是相当困难的。
```
# 基本思想及策略
## 分治思想
分治法的设计思想是:将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。
## 分治策略
分治策略是:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地求解这些子问题,然后将各子问题的解合并得到原问题的解。这种算法设计策�
点击阅读更多
资源评论
StoneChan
- 粉丝: 27
- 资源: 321
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功