说说你对分而治之、动态规划的理解?区别?

这篇具有很好参考价值的文章主要介绍了说说你对分而治之、动态规划的理解?区别?。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

说说你对分而治之、动态规划的理解?区别?

一、分而治之

分而治之是算法设计中的一种方法,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并

关于分而治之的实现,都会经历三个步骤:

  • 分解:将原问题分解为若干个规模较小,相对独立,与原问题形式相同的子问题
  • 解决:若子问题规模较小且易于解决时,则直接解。否则,递归地解决各子问题
  • 合并:将各子问题的解合并为原问题的解

实际上,关于分而治之的思想,我们在前面已经使用,例如归并排序的实现,同样经历了实现分而治之的三个步骤:

  • 分解:把数组从中间一分为二

  • 解决:递归地对两个子数组进行归并排序

  • 合并:将两个字数组合并称有序数组

同样关于快速排序的实现,亦如此:

  • 分:选基准,按基准把数组分成两个字数组
  • 解:递归地对两个字数组进行快速排序
  • 合:对两个字数组进行合并

同样二分搜索也能使用分而治之的思想去实现,代码如下:

function binarySearch(arr,l,r,target){
    if(l> r){
        return -1;
    }
    let mid = l + Math.floor((r-l)/2)
    if(arr[mid] === target){
        return mid;
    }else if(arr[mid] < target ){
        return binarySearch(arr,mid + 1,r,target)
    }else{
        return binarySearch(arr,l,mid - 1,target)
    }
}

二、动态规划

动态规划,同样是算法设计中的一种方法,是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法

常常适用于有重叠子问题和最优子结构性质的问题

简单来说,动态规划其实就是,给定一个问题,我们把它拆成一个个子问题,直到子问题可以直接解决

然后呢,把子问题答案保存起来,以减少重复计算。再根据子问题答案反推,得出原问题解的一种方法。

一般这些子问题很相似,可以通过函数关系式递推出来,例如斐波那契数列,我们可以得到公式:当 n 大于 2的时候,F(n) = F(n-1) + F(n-2) ,

f(10)= f(9)+f(8),f(9) = f(8) + f(7)...是重叠子问题,当n = 1、2的时候,对应的值为2,这时候就通过可以使用一个数组记录每一步计算的结果,以此类推,减少不必要的重复计算

适用场景

如果一个问题,可以把所有可能的答案穷举出来,并且穷举出来后,发现存在重叠子问题,就可以考虑使用动态规划

比如一些求最值的场景,如最长递增子序列、最小编辑距离、背包问题、凑零钱问题等等,都是动态规划的经典应用场景

关于动态规划题目解决的步骤,一般如下:

  • 描述最优解的结构
  • 递归定义最优解的值
  • 按自底向上的方式计算最优解的值
  • 由计算出的结果构造一个最优解

三、区别

动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解

与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的,而分而治之的子问题是相互独立的

若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次

如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间

综上,可得:

  • 动态规划:有最优子结构和重叠子问题

  • 分而治之:各子问题独立

参考文献

  • https://baike.baidu.com/item/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/529408
  • https://juejin.cn/post/6951922898638471181

如果对您有所帮助,欢迎您点个关注,我会定时更新技术文档,大家一起讨论学习,一起进步。

 说说你对分而治之、动态规划的理解?区别?文章来源地址https://www.toymoban.com/news/detail-858990.html

到了这里,关于说说你对分而治之、动态规划的理解?区别?的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 说说你对栈、队列的理解?应用场景?

    栈(stack)又名堆栈,它是一种运算受限的线性表,限定仅在表尾进行插入和删除操作的线性表 表尾这一端被称为栈顶,相反地另一端被称为栈底,向栈顶插入元素被称为进栈、入栈、压栈,从栈顶删除元素又称作出栈 所以其按照先进后出的原则存储数据,先进入的数据被压

    2024年04月11日
    浏览(49)
  • 说说你对堆的理解?如何实现?应用场景?

    堆(Heap)是计算机科学中一类特殊的数据结构的统称 堆通常是一个可以被看做一棵完全二叉树的数组对象,如下图: 总是满足下列性质: 堆中某个结点的值总是不大于或不小于其父结点的值 堆总是一棵完全二叉树 堆又可以分成最大堆和最小堆: 最大堆:每个根结点,都有根

    2024年04月22日
    浏览(45)
  • 说说你对图的理解?相关操作有哪些?

    在计算机科学中,图是一种抽象的数据类型,在图中的数据元素通常称为结点, V 是所有顶点的集合, E 是所有边的集合 如果两个顶点 v , w ,只能由 v 向 w ,而不能由 w 向 v ,那么我们就把这种情况叫做一个从  v  到  w  的有向边。 v 也被称做初始点, w 也被称为终点。这

    2024年04月22日
    浏览(48)
  • 说说你对集合的理解?常见的操作有哪些?

    集合(Set),指具有某种特定性质的事物的总体,里面的每一项内容称作元素 在数学中,我们经常会遇到集合的概念: 有限集合:例如一个班集所有的同学构成的集合 无限集合:例如全体自然数集合 在计算机中集合道理也基本一致,具有三大特性: 确定性:于一个给定的

    2024年04月16日
    浏览(71)
  • 说说你对树的理解?相关的操作有哪些?

    在计算机领域,树形数据结构是一类重要的非线性数据结构,可以表示数据之间一对多的关系。以树与二叉树最为常用,直观看来,树是以分支关系定义的层次结构 二叉树满足以下两个条件: 本身是有序树 树中包含的各个结点的不能超过 2,即只能是 0、1 或者 2 如下图,左

    2024年04月17日
    浏览(51)
  • 说说你对归并排序的理解?如何实现?应用场景?

    归并排序(Merge Sort)是建立归并操作上的一种有效,稳定的排序算法,该算法是采用分治法的一个非常典型的应用 将已有序的子序列合并,得到完全有序的序列,即先使每个子序列有序,再使子序列段间有序 例如对于含有  n  个记录的无序表,首先默认表中每个记录各为一

    2024年04月24日
    浏览(70)
  • 说说你对二分查找的理解?如何实现?应用场景?

      在计算机科学中,二分查找算法,也称折半搜索算法,是一种在有序数组中查找某一特定元素的搜索算法 想要应用二分查找法,则这一堆数应有如下特性: 存储在数组中 有序排序 搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束 如果

    2024年04月25日
    浏览(41)
  • 说说你对选择排序的理解?如何实现?应用场景?

    选择排序(Selection sort)是一种简单直观的排序算法,无论什么数据进去都是  O(n²) 的时间复杂度,所以用到它的时候,数据规模越小越好 其基本思想是:首先在未排序的数列中找到最小(or最大)元素,然后将其存放到数列的起始位置 然后再从剩余未排序的元素中继续寻找最

    2024年04月23日
    浏览(44)
  • 说说你对贪心算法、回溯算法的理解?应用场景?

    贪心算法,又称贪婪算法,是算法设计中的一种思想 其期待每一个阶段都是局部最优的选择,从而达到全局最优,但是结果并不一定是最优的 举个零钱兑换的例子,如果你有1元、2元、5元的钱币数张,用于兑换一定的金额,但是要求兑换的钱币张数最少 如果现在你要兑换

    2024年04月28日
    浏览(47)
  • 说说你对数据结构的理解?有哪些?区别?

    数据结构是计算机存储、组织数据的方式,是指相互之间存在一种或多种特定关系的数据元素的集合 前面讲到,一个程序 = 算法 + 数据结构,数据结构是实现算法的基础,选择合适的数据结构可以带来更高的运行或者存储效率 数据元素相互之间的关系称为结构,根据数据元

    2024年04月10日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包