首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
基础学习课
实战项目课
求职辅导课
专栏&文章
竞赛
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
AI面试、笔试、校招、雇品
HR免费试用AI面试
最新面试提效必备
登录
/
注册
VLK_hf
河北经贸大学 测试其它
发布于河北
关注
已关注
取消关注
@编程文青李狗蛋:
分治算法,分而治之!
大家好呀,我是帅蛋。 在上一篇文章中我讲了递归算法: 递归不会,有点崩溃! 递归是一种很重要的算法,经常在一些高级的算法中应用,比如今天我要讲的分治算法。 分治算法同样也是一种很重要的算法,可能很多同学都听说过分治算法,但是没有系统的了解过。 这篇文章,就让我们来一探究竟。 这篇是我在牛客网连载系列 #帅蛋的数据结构与算法空间#的第 9 篇文章,欢迎大家关注。 也希望大家能够喜欢上帅蛋,多多点赞收藏,记得关注我呀! 什么是分治? 学习分治,得先知道什么是分治。 分治,表面意思就是“分而治之”,洋名儿叫 Divde & Conquer。 正规点的说法是: 分治算法就是将一个大的复杂的问题,拆分成多个相同或者相似的子问题,然后再把子问题拆成更小的子问题,然后再拆成更更小的问题 and so on 直至最后的子问题可以简单求解,那最后问题的解即子问题解的合并。 白话点说就是: 将一个难题,拆成一些规模较小的相同的子问题,各个击破,分而治之。 很多算法用到了分治的思想,比如排序算法中的快排和归并排序,这些等我讲到排序算法的时候再来细聊。 由此可以看出,分治算法真真正正是一种处理问题的思想,这个要区别于递归,递归只是一种编程技巧。 分治算法的过程 分治算法由“分”和“治”两部分组成,但是它主要包括 3 个过程: 划分(Divide) 求解(Conquer) 合并(Combine) 其中: 划分(Divide):将原问题划分为规模较小的子问题,子问题相互独立,与原问题形式相同。 求解(Conquer):递归的求解划分之后的子问题。 合并(Combine):这一步非必须。有些问题涉及合并子问题的解,将子问题的解合并成原问题的解。有的问题则不需要,只是求出子问题的解即可。 分治算法的整个流程可以看下图: 分治算法适用情况 由分治算法的过程可以看出分治算法适用的情况,我的总结是 4 个词: 规模大 可分解 各独立 可合并 “规模大”和“可分解”针对原始问题。 即原问题要规模比较大,不易直接解决,但是问题分解成规模较小的相同子问题比较容易解决。 “各独立”和“可合并”针对子问题。 即子问题之间求解是相关独立互不影响,且子问题的解可以合并成原始问题的解。 这四个词中最重要的是“各独立”和“可合并”。 “各独立”涉及到分治法的效率问题。 如果各个子问题是不独立的,则分治法就需要重复的去解决一些重复的子问题,这样多做了很多不必要的工作。 比如我们很熟悉的斐波那契数列,公式如下: 假设我们要求 f(5),分治法将其划分为一个个的子问题: 由上图可见,仅仅是求 f(5),仅仅是只画了 3 层,就已经出现了相同结果的重复计算(比如 f(3) 和 f(2))。 通过对子问题解的合并,最终的结果毋庸置疑,但是因为各个子问题的不独立,造成了子问题的重复计算,从而分治法求解斐波那契的效率感人... 碰到这种情况,还是动态规划比较合适... “可合并”是涉及能否用分治的关键。 如果子问题的解可合并,那就能用分治法。 如果不可合并,单单只是“规模大”和“可分解”,分治就没必要考虑,用贪心或者动态规划才是正理。 设计分治算法 通过之前的了解,其实可以很清楚的发现,用分治算法解决问题的核心,其实就是归纳一个求解的数学公式,然后根据公式设计递归程序。 说白了就是先找找拆分到最小规模问题时怎么解,然后再瞅瞅随着问题规模增大点问题怎么解,最后就是找到递归函数,码出递归代码即可。 分治算法实例 其实在这之前,我已经讲过一个典型的分治算法的应用:二分查找。 可以说二分查找是分治算法中最常用的算法: ACM 选手带你玩转二分查找! 二分查找是在一个有序的数组中进行查找吗,每次可以让问题的规模减半。 它思路比较简单: 选择一个 mid 将数组分为左右两个集合。 判断标志 arr[mid] 是否能与要查找的目标值 target 相等,相等则直接返回。 若小于 arr[mid],则在左半区间继续查找。 如大于 arr[mid],则在右半区继续查找。 递归上面的步骤。 def BinarySearch(arr, low, high, target): if low <= high: mid = (low + high) / 2 if arr[mid] == target: return mid elif arr[mid] < target: return BinarySearch(arr, low, mid - 1, target) else: return BinarySearch(arr, mid + 1, high, target) else: # 没有找到 return -1 分治算法到这就讲完辣,原理很简单,大家看会了么? 原理搞懂只是迈出学会分治算法的第一步,想要灵活的使用却不是一件容易的事儿,更多的还是要在实战中领悟,在实战中加深对分治算法的理解。 大家只要认真去搞,就一定能掌握分治算法。 我是帅蛋,我们下次见。 ❤️ 欢迎关注我,有问题,找帅蛋,我最看不得别人迷茫! ❤️ 如果你觉得有帮助,希望爱学习的你不要吝啬三连击哟[点赞 + 收藏 + 评论]~ 还有小小公众号 【编程文青李狗蛋】,聊聊迷茫吹吹牛皮~
点赞 14
评论 4
全部评论
推荐
最新
楼层
暂无评论,快来抢首评~
相关推荐
昨天 11:14
北京科技大学 C++
好真实的互联网鄙视链
互联网大厂内部鄙视链大揭秘在互联网大厂里,各个部门都觉得自己是公司不可或缺的一部分,所以当问起哪个部门最重要时,每个部门都有自己的答案。今天我们就来揭秘一下互联网大厂内部的鄙视链。运营部:无我即无一切 🌐运营部的人认为自己才是公司的大脑,没有他们,公司就啥也干不了。毕竟,运营负责整个公司的生意计划、组织、实施和控制,是产品生产和服务创造的核心。但在其他部门眼里,运营部就是个无脑提需求的,测试部门觉得他们整天无所事事。这其实也很正常,毕竟每个部门都有自己的工作重点。市场部:卖货的王者 🛒市场部的人觉得自己是公司的销售冠军,没有他们,公司根本没法儿活。他们认为自己卖出去的产品才是公司的命脉。但...
点赞
评论
收藏
分享
07-24 17:45
迅雷_X-PEP 产品星(准入职员工)
迅雷内推
入职迅雷这种老牌互联网公司之后我后悔了后悔没有早点入职哈哈哈,虽然比不上那些一线互联网大厂,但是福利待遇方面真的没得说,待遇上一点也不比一线的差,而且对我们应届生真的太友好了 首先在福利方面,除了超级大方的薪资外每个月还有900块钱的餐补,每天还有免费的零食咖啡饮料提供,我每天最快乐的事情就是去冰柜里挑选我的工作搭子搭哈哈🤗 最最最最重要的是迅雷对实习生和校招生的培养真的有上心,有内部的一套培养方法论,入职不久我已经学到超多知识了,而且带我的mentor也好好呀,每天对我各种投喂好幸福呀迅雷2026届X-PEP产品星计划今日正式启动项目简介:X-PEP是迅雷集团面向全球校园优秀人才推出的产品...
迅雷公司福利 83人发布
点赞
评论
收藏
分享
06-22 21:02
广东药科大学 Java
请问这是在招奴隶吗
这种公司就赶紧避雷吧,有bug半夜也要起来?还学习腾讯,自己几斤几两不清楚吗
Java大菜狗:
纯纯招黑奴,一天还不到两百那么多要求,还不迟到早退,以为啥啊,给一点工资做一堆活,还以不拖欠员工工资为荣,这是什么值得骄傲的事情吗,纯纯***公司
点赞
评论
收藏
分享
07-22 13:43
门头沟学院 测试工程师
秋招第一面
有点焦虑
点赞
评论
收藏
分享
评论
点赞成功,聊一聊 >
点赞
收藏
分享
评论
提到的真题
返回内容
全站热榜
更多
1
...
实习包装不是吹牛皮,要怎么包装看这里
4.7W
2
...
百度提前批一面 7.24
6949
3
...
字节复活赛
6514
4
...
百度一二面凉经
5428
5
...
入我滴滴!早十晚六 !
3319
6
...
百度一面面经7.14
2927
7
...
再再再再强调一遍!秋招不要装逼
2655
8
...
滴滴提前批面经
2655
9
...
百度提前批一面:面试官居然让我手撕两数之和???最奇幻的一轮面试,结束还说.......
2261
10
...
百度二面面筋
2180
创作者周榜
更多
正在热议
更多
#
哪些公司开提前批了?
#
24445次浏览
255人参与
#
你今年的平均薪资是多少?
#
133868次浏览
685人参与
#
风评不好的公司,你会去吗?
#
57633次浏览
418人参与
#
实习如何「偷」产出?
#
48514次浏览
1268人参与
#
正在春招的你,也参与了去年秋招吗?
#
312623次浏览
2528人参与
#
除了主业以外,你还有哪些其他收入?
#
11371次浏览
196人参与
#
互联网公司评价
#
401096次浏览
3836人参与
#
你最满意的offer薪资是哪家公司?
#
32974次浏览
176人参与
#
节后第一天上班,我的精神状态
#
13378次浏览
117人参与
#
不卡学历的大厂有哪些?
#
27160次浏览
217人参与
#
校招阶段,学历VS技术哪个更重要?
#
16645次浏览
182人参与
#
职场新人体验
#
23868次浏览
231人参与
#
签约/解约注意事项
#
696829次浏览
4068人参与
#
应届生初入职场,求建议
#
229664次浏览
2642人参与
#
你投递的公司有几家约面了?
#
108770次浏览
778人参与
#
腾讯音乐求职进展汇总
#
97989次浏览
570人参与
#
校园里的破防时刻
#
10613次浏览
122人参与
#
硬件人求职现状
#
434439次浏览
4539人参与
#
正在实习的碎碎念
#
1454217次浏览
13469人参与
#
宁德时代求职进展汇总
#
122693次浏览
650人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务