常用算法之分治算法 常用算法之分治算法是什么
yuyutoo 2024-10-12 00:59 1 浏览 0 评论
分治法是一种很重要的算法，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
基本思想及策略
分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
分治法适用的情况
1) 该问题的规模缩小到一定的程度就可以容易地解决。
2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
3) 利用该问题分解出的子问题的解可以合并为该问题的解。
4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
分治法的基本步骤
1、分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
2、解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
3、合并：将各个子问题的解合并为原问题的解。
算法设计模式
Divide-and-Conquer(P)
1. if |P|≤n0
2. then return(ADHOC(P))
3. 将P分解为较小的子问题 P1 ,P2 ,...,Pk
4. for i←1 to k
5. do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi
6. T ← MERGE(y1,y2,...,yk) △ 合并子问题
7. return(T)
其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。ADHOC(P)是该分治法中的基本子算法，用于直接解小规模的问题P。算法MERGE(y1,y2,...,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,...,Pk的相应的解y1,y2,...,yk合并为P的解。
分治法的复杂性分析
一个分治法将规模为n的问题分成k个规模为n／m的子问题去解。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：
T（n）= k T(n/m)+f(n)
递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由n等于m的方幂时,T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的，从而当 mi≤n<mi+1时，T(mi)≤T(n)<T(mi+1)。
分治法设计的思维过程
实际上就是类似于数学归纳法，找到解决本问题的求解方程公式，然后根据方程公式设计递归程序。
1、一定是先找到最小问题规模时的求解方法。
2、然后考虑随着问题规模增大时的求解方法。
3、找到求解的递归函数式后（各种规模或因子），设计递归程序即可。
相关推荐
- jQuery VS AngularJS 你更钟爱哪个?
-
在这一次的Web开发教程中，我会尽力解答有关于jQuery和AngularJS的两个非常常见的问题，即jQuery和AngularJS之间的区别是什么？也就是说jQueryVSAngularJS？...
- Jquery实时校验，指定长度的「负小数」，小数位未满末尾补0
-
在可以输入【负小数】的输入框获取到焦点时，移除千位分隔符，在输入数据时，实时校验输入内容是否正确，失去焦点后，添加千位分隔符格式化数字。同时小数位未满时末尾补0。HTML代码...
- 如何在pbootCMS前台调用自定义表单?pbootCMS自定义调用代码示例
-
要在pbootCMS前台调用自定义表单，您需要在后台创建表单并为其添加字段，然后在前台模板文件中添加相关代码，如提交按钮和表单验证代码。您还可以自定义表单数据的存储位置、添加文件上传字段、日期选择器、...
- 编程技巧:Jquery实时验证，指定长度的「负小数」
-
为了保障【负小数】的正确性，做成了通过Jquery，在用户端，实时验证指定长度的【负小数】的方法。HTML代码<inputtype="text"class="forc...
- 一篇文章带你用jquery mobile设计颜色拾取器
-
【一、项目背景】现实生活中，我们经常会遇到配色的问题，这个时候去百度一下RGB表。而RGB表只提供相对于的颜色的RGB值而没有可以验证的模块。我们可以通过jquerymobile去设计颜色的拾取器...
- 编程技巧:Jquery实时验证，指定长度的「正小数」
-
为了保障【正小数】的正确性，做成了通过Jquery，在用户端，实时验证指定长度的【正小数】的方法。HTML做成方法<inputtype="text"class="fo...
- jquery.validate检查数组全部验证
-
问题：html中有多个name[]，每个参数都要进行验证是否为空，这个时候直接用required:true话，不能全部验证，只要这个数组中有一个有值就可以通过的。解决方法使用addmethod...
- Vue进阶(幺叁肆):npm查看包版本信息
-
第一种方式npmviewjqueryversions这种方式可以查看npm服务器上所有的...
- layui中使用lay-verify进行条件校验
-
一、layui的校验很简单，主要有以下步骤：1.在form表单内加上class="layui-form"2.在提交按钮上加上lay-submit3.在想要校验的标签，加上lay-...
- jQuery是什么?如何使用? jquery是什么功能组件
-
jQuery于2006年1月由JohnResig在BarCampNYC首次发布。它目前由TimmyWilson领导,并由一组开发人员维护。jQuery是一个JavaScript库，它简化了客户...
- django框架的表单form的理解和用法-9
-
表单呈现...
- jquery对上传文件的检测判断 jquery实现文件上传
-
总体思路：在前端使用jquery对上传文件做部分初步的判断，验证通过的文件利用ajaxFileUpload上传到服务器端，并将文件的存储路径保存到数据库。<asp:FileUploadI...
- Nodejs之MEAN栈开发(四)-- form验证及图片上传
-
这一节增加推荐图书的提交和删除功能，来学习node的form提交以及node的图片上传功能。开始之前需要源码同学可以先在git上fork：https://github.com/stoneniqiu/R...
- 大数据开发基础之JAVA jquery 大数据java实战
-
上一篇我们讲解了JAVAscript的基础知识、特点及基本语法以及组成及基本用途，本期就给大家带来了JAVAweb的第二个知识点jquery，大数据开发基础之JAVAjquery，这是本篇文章的主要...
- 推荐四个开源的jQuery可视化表单设计器
-
jquery开源在线表单拖拉设计器formBuilder(推荐)jQueryformBuilder是一个开源的WEB在线html表单设计器，开发人员可以通过拖拉实现一个可视化的表单。支持表单常用控件...
欢迎 你 发表评论:
- 一周热门
- 最近发表
- 标签列表
-
- mybatis plus (70)
- scheduledtask (71)
- css滚动条 (60)
- java学生成绩管理系统 (59)
- 结构体数组 (69)
- databasemetadata (64)
- javastatic (68)
- jsp实用教程 (53)
- fontawesome (57)
- widget开发 (57)
- vb net教程 (62)
- hibernate 教程 (63)
- case语句 (57)
- svn连接 (74)
- directoryindex (69)
- session timeout (58)
- textbox换行 (67)
- extension_dir (64)
- linearlayout (58)
- vba高级教程 (75)
- iframe用法 (58)
- sqlparameter (59)
- trim函数 (59)
- flex布局 (63)
- contextloaderlistener (56)