侯体宗的博客
  • 首页
  • Hyperf版
  • beego仿版
  • 人生(杂谈)
  • 技术
  • 关于我
  • 更多分类
    • 文件下载
    • 文字修仙
    • 中国象棋ai
    • 群聊
    • 九宫格抽奖
    • 拼图
    • 消消乐
    • 相册

前端实现分而治之、动态规划算法

前端  /  管理员 发布于 6年前   495
目录
一、分而治之
二、动态规划
适用场景
三、区别
参考文献

design1

# 面试官:说说你对分而治之、动态规划的理解?区别?

# 一、分而治之

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

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

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

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

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

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

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

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

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

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

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

  • 上一条:
    前端实现冒泡排序(Bubble Sort)
    下一条:
    前端实现贪心算法,又称贪婪算法、回溯算法
  • 昵称:

    邮箱:

    0条评论 (评论内容有缓存机制,请悉知!)
    最新最热
    • 分类目录
    • 人生(杂谈)
    • 技术
    • linux
    • Java
    • php
    • 框架(架构)
    • 前端
    • ThinkPHP
    • 数据库
    • 微信(小程序)
    • Laravel
    • Redis
    • Docker
    • Go
    • swoole
    • Windows
    • Python
    • 苹果(mac/ios)
    • 相关文章
    • 在Nuxt3中如何减少import model声明及初始化加载models快速开发秘诀(0个评论)
    • 在js的websocket客户端开发中遇到代码割裂情况解决方案(0个评论)
    • 在uni-app中使用Ucharts柱状图地步横向滚动条无法滑动解决方式(0个评论)
    • 在vue中实现移动端双指放大或缩小功能代码示例(0个评论)
    • jq中实现图片压缩、base64转成file后上传至服务器示例(0个评论)
    • 近期文章
    • 在Nuxt3中如何减少import model声明及初始化加载models快速开发秘诀(0个评论)
    • 适用于 Laravel 的表单请求测试程序包(0个评论)
    • Laravel 10.25版本发布(0个评论)
    • 在go语言中实现生成文件的校验和功能代码示例(0个评论)
    • Laravel 11版本抢先看,看将有什么新功能发布(0个评论)
    • goose数据库迁移工具介绍及使用流程步骤(0个评论)
    • 中国程序员“翻墙”为海外软件公司打工,105.8万工资被罚没!转知乎(0个评论)
    • 在go语言gin框架中使用Sharding(Gorm分表中间件)实现分表流程步骤(0个评论)
    • 在PHP提高性能方式之开启OPCache扩展及OPCache配置参数详解(0个评论)
    • 在js的websocket客户端开发中遇到代码割裂情况解决方案(0个评论)
    • 近期评论
    • 路人 在

      php中使用hyperf框架调用讯飞星火大模型实现国内版chatgpt功能示例中评论 教程很详细,如果加个前端chatgpt对话页面就完美了..
    • 博主 在

      科学上网翻墙之v2rayN-Core客户端免费公益节点使用教程中评论 @ mashrdn 多切换几个节点测试,免费ssr是没那么稳..
    • mashrdn 在

      科学上网翻墙之v2rayN-Core客户端免费公益节点使用教程中评论 V2rayn免费节点添加上去了,youtobe无法打开网页,是怎么回事..
    • 张伟 在

      科学上网翻墙之v2rayN-Core客户端免费公益节点使用教程中评论 3q!有用,不过免费节点隔天就要去git上复制新的导进去..
    • 博主 在

      科学上网翻墙访问Google , 上外网神器佛跳墙VPN(永久免费)使用流程步骤中评论 该篇教程已不能用了,告知大家,免的老有老铁问我!..
    • 2016-10
    • 2016-11
    • 2017-06
    • 2017-07
    • 2017-08
    • 2017-09
    • 2017-10
    • 2017-11
    • 2018-03
    • 2018-04
    • 2018-05
    • 2018-06
    • 2018-09
    • 2018-11
    • 2018-12
    • 2019-02
    • 2020-03
    • 2020-04
    • 2020-05
    • 2020-06
    • 2021-04
    • 2021-05
    • 2021-07
    • 2021-08
    • 2021-09
    • 2021-10
    • 2021-11
    • 2022-08
    • 2022-09
    • 2022-10
    • 2022-11
    • 2022-12
    • 2023-01
    • 2023-02
    • 2023-03
    • 2023-04
    • 2023-05
    • 2023-06
    • 2023-07
    • 2023-09
    Top

    Copyright·© 2019 侯体宗版权所有· 粤ICP备20027696号 PHP交流群

    侯体宗的博客