基本算法-分治

  • 分治算法
万子德·中国科学院大学
2016-02-04
阅读数152

引言

凡治众如治寡,分数是也。                        ----孙子兵法

思想

对k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止。

然后将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。

分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。

分治与递归

由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。

分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。

分治与其他算法

采用分治思想的算法有很多,例如:二分查找、快速排序、合并排序、矩阵乘法等等

分治算法的应用

分治算法的具体应用请用请参考:二分查找、快速排序、合并排序、矩阵乘法等相关知识点。

written by 金磊,隔日更新一发,转载请注明出处。

本文由 万子德 授权 赛氪网 发表,并经赛氪网编辑。转载此文章须经作者同意,并请附上出处(赛氪网)及本页链接。原文链接https://www.saikr.com/a/2567
收藏
分享
别默默的看了,快来和大家聊聊吧,登录后发表评论~ 登录 立即注册
打赏
万子德
打赏金额(金额:¥0)
给Ta留言
赏金已入袋,多谢!(*^__^*)
温馨提示

非常抱歉!本站不支持旧版本IE浏览器~~建议使用IE10/IE11/Chrome/Firefox/Safari等高级浏览器浏览。

温馨提示
温馨提示
帮助与反馈

热门问题