五大常用算法之四:分治法

2023-11-10

分治法和动态规划有点像,都是分解成子问题

中科大的张署老师课件很清楚,摘录如下:

1.什么是分治法

     当求解的问题较复杂或规模较大时,不能立刻得到原问题的解,但这些问题本身具有这样的特点,它可以分解为若干个与原问题性质相类似的子问题,而这些子问题较简单可方便得到它们的解,因此通过合并这些子问题的解就可得到原问题的解。

2. 应用分治法的三个基本步骤

①分解问题(divide):把原问题分解为若干个与原问题性质相类似的子问题

②求解子问题(conquer):不断分解子问题直到可方便求出子问题的解为止

③合并子问题的解(combine):合并子问题的解得到原问题的解

做题时的三步(与上面类似)

①divide:把具有n个元素的数组分解为二个n/2大小的子数组

②conquer:递归地分解子数组,直到子数组只包含一个元素为止

③combine:二二合并已排好序的子数组使之成为一个新的排好序的子数组,重复这样二二合并的过程直到得到原问题的解

 

3.分治法适用条件

①原问题可以分解为若干个与原问题性质相类似的子问题

②问题的规模缩小到一定程度后可方便求出解

③子问题的解可以合并得到原问题的解

④分解出的各个子问题应相互独立,即不包含重叠子问题

   如求Fib数问题

 

4.经典例子:

归并排序(Merge Sort) 思想:如果能把原待排序的数组分解成若干个待排序的子数组,而这些子数组可以方便地排好序,并且通过合并这些子数组的解将能得到原问题的解,则整个数组将排好序。

快速排序:

二分查找:一个有序数组,通过均匀二分,每次折半查找,不就是分治法吗!!!

FFT快速傅里叶变换:这是DSP课本里的知识,离散时域信号转换为频域信号,运算量太大,故拆分计算再合并,每部分的处理方式和没拆分时总体的方式一样的,所以符合分治法!!!

 

5.三种常用算法:

替换法,递归树,主方法

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

五大常用算法之四:分治法 的相关文章

  • 事务并发问题及事务隔离级别的学习

    以下内容都是看的咕泡学院的大神老师讲的一个公开课 就是记录一下 事务并发带来的三大问题 1 脏读 如下图 左右两个事务A B 事务A首先查询id 1的数据 得到age 16之后 事务B对id 1的数据 将age 16更新为age 18 然后

随机推荐

  • STM32驱动步进电机(原理、程序、解决电机只震动不转动问题)

    一 步进电机的介绍 首先来看一下步进电机的样子 本介绍采用平时最常见也是最简单的28BYJ 48 这是一个五线四项电机 五线 顾名思义 外部五条线 四项 电机内部的定子上有8个齿 正对着的2个齿上的绕组又是串联在一起的 也就是说正对着的2个
  • STM32CUBE 定时器使用

    目录 STM32F407VET6 定时中断 记录各个STM32型号的定时器使用方法 包括定时中断 输入捕获等功能 持续更新 STM32F407VET6 定时中断 时钟配置 这里主频配置为100Mhz 最高168Mhz 即HCLK 100MH
  • [用python辅助学生中考与高考-1]:家长篇-科技特长生概述与优势

    目录 前言 这是科技的最好时代 1 什么是科技特长生 2 科技特长生的优势 科技特长生录取方式 3 科技特长生的类型 4 科技特长生七大招生类目 5 如何成为科技特长生 6 常见的赛事 前言 这是科技的最好时代 随着国家强基计划的出台和国际
  • java编程之java jwt token什么是JWT?(一)

    转自 http www leftso com blog 220 html 一 什么是JWT 了解JWT 认知JWT 首先jwt其实是三个英语单词JSON Web Token的缩写 通过全名你可能就有一个基本的认知了 token一般都是用来认
  • 房屋租赁系统

    java房屋租赁系统
  • RFC文档:官网、中文RFC文档 及 HTTP/2相关文档

    记录一下RFC的官方文档 2023 06 12修正中文RFC文档无法访问问题 一 RFC官方网站 http www rfc editor org Index of rfc RFC文档列表 Index of rfc 二 中文RFC文档 中文R
  • OS面试题(转载)

    转载自 http placement freshersworld com power preparation technical interview preparation os interview questions 23351 1 Wh
  • Tracy 小笔记 Vue - Vue 对象

    Vue 对象 const vue new Vue options el 类型 String HtmlElement 作用 挂载对象 决定之后Vue 对象会管理哪个 Dom template 当同时有 el 和 tempalte 的时候这里写
  • java泛型

    一 泛型概念的提出 为什么需要泛型 首先 我们看下下面这段简短的代码 1 public class GenericTest 2 3 public static void main String args 4 List list new Ar
  • 计算机文档加密如何解锁,bitlocker怎么解锁_bitlocker解锁方法

    许多用户为了保护电脑文件安全不被偷看 都会喜欢使用bitlocker加密功能来进行加密 Bitlocker是一种独特的为磁盘添加密码的工具 但是很多用户使用bitlocke加密完之后 不知道要怎么解锁 为此小编这就给大家带来bitlocke
  • Vue 使用 mqttws31.js 实现消息实时推送功能(WebSocket)

    1 在 vue 文件中引入 mqttws31 js 文件 mqttws31 js 文件代码在本页底部 import utils mqttws31 2 在 vue 文件中添加代码 export default data return clie
  • MapReduce官方案例wordcount

    wordcountReduce java package MaperReduce import java io IOException import org apache hadoop io LongWritable import org
  • Python后端Flask学习项目实践---搭建一个问答网站

    1 项目效果展示 这里主要以后端为主 前端的代码不做展示 如果需要代码可以评论或者私信 用户注册 登录相关 用邮箱进行注册 并通过向邮箱发送验证码来进行判断 一个邮箱只能注册一个账号 首页相关 用户登录后可以进行发布问题和回答 同时也提供搜
  • 外罚函数法计算机,罚函数法与障碍函数法

    罚函数法与障碍函数法 罚函数法与障碍函数法是求解约束极小化问题的较好的算法 其基本原理是在原目标函数中加上一个罚 障碍 函数 而得到一个增广目标函数 罚 障碍 函数的功能是对非可行或企图穿越边界而逃离可行域的点赋予一个极大的函数值 可以作一
  • 使用 Date 和 SimpleDateFormat 类表示时间以及Calendar 类的应用

    在程序开发中 经常需要处理日期和时间的相关数据 此时我们可以使用 java util 包中的 Date 类 这个类最主要的作用就是获取当前时间 我们来看下 Date 类的使用 使用 Date 类的默认无参构造方法创建出的对象就代表当前时间
  • sql:SQL优化知识点记录(七)

    1 索引优化5 2 索引优化6 3 索引优化7 查询 百分号加右边 否则索引会失效 没建立索引之前都是全表扫描 没建立索引 建立索引 建立索引 id是主键 他也可以从主键上取 覆盖索引要到了name 索引没有失效 覆盖索引要到了age 索引
  • 使用OpenCV,Python和dlib进行眨眼检测及计数

    前三篇博客学习了 windows10 Python3 7安装dlib库进行面部标志识别 python dlib实现面部标志识别 使用python dlib OpenCV提取眼睛 鼻子 嘴唇及下颌 这篇博客将进行进阶版的学习 眨眼检测 眨眼检
  • 如何利用codesense的GJB8114模板对c++源码进行进行规则检测

    2013年7 10 中国 民解放军总装备部发布了中华 民共和国国家军 标准GJB 8114 全称为 8114 2013 C C 语 编程安全 集 提出软件编程标准 以提 国家军 软件的安全性 并作为静态规则检查的依据 量数据表明 软件存在的
  • Python可视化图系列(1)-----jupyter notebook

    Python可视化 复杂的散点图 文章目录 Python可视化 复杂的散点图 前言 一 我们的目标是什么 二 实现目标的知识准备 1 引入库 2 导入数据 3 准备标签的列表和颜色 三 画目标图片 复杂的散点图 四 解读图像 总结 前言 提
  • 五大常用算法之四:分治法

    分治法和动态规划有点像 都是分解成子问题 中科大的张署老师课件很清楚 摘录如下 1 什么是分治法 当求解的问题较复杂或规模较大时 不能立刻得到原问题的解 但这些问题本身具有这样的特点 它可以分解为若干个与原问题性质相类似的子问题 而这些子问