最近才捡起的算法设计与分析.分析不准确的地方谅解,请各位看官指正.
1. 分治法与动态规划主要共同点:
二者都要求原问题具有最优子结构性质,都是将原问题分而治之,分解成若干个规模较小(小到很容易解决的程序)的子问题.然后将子问题的解合并,形成原问题的解.
2. 分治法与动态规划实现方法:
① 分治法通常利用递归求解.
② 动态规划通常利用迭代法自底向上求解,但也能用具有记忆功能的递归法自顶向下求解.
3. 分治法与动态规划主要区别:
① 分治法将分解后的子问题看成相互独立的.
② 动态规划将分解后的子问题理解为相互间有联系,有重叠部分.
例如: 在求解斐波那契数列过程中,求解fibonacci(5)时,得求解fibonacci(4)和fibonacci(3).其中,求解fibonacci(4)时,需要求解fibonacci(3).
在分治法中,求解完fibonacci(4)后还得重新求解fibonacci(3),即使求解fibonacci(4)子问题的时候已经求解过,也就是说,求解了二次子问题fibonacci(3).
动态规划为了避免类似子问题fibonacci(3)的重复求解,将已经求解过的子问题的解保存下来,在需要的时候将解值取出来,省去子问题解的重复求解过程.
4. 分治法与动态规划适用条件:
① 原问题具有最优子结构性质的前提下,分解出的子问题都绝对相互独立.
② 原问题具有最优子结构性质的前提下,分解出的子问题并不相互独立,求解一个子问题可能要用到已经求解过的子问题的解,子问题间具有重叠性,即适合具有重叠子问题性质的原问题.
5. 分治法与动态规划复杂度分析:
① 分治法因为对子问题进行了多次求解,所以效率比动态规划低一点.(时间复杂度相对高)
② 动态规划求解需要将子问题的解保存下来,所以会比分治法多用一些空间.(空间复杂度相对高)
其实,算法世界里,要么用时间换空间,要么用空间换时间.
分享到:
相关推荐
动态规划法与分治法的区别 动态规划法与贪心法的区别 分枝限界法与回溯法的异同 等自己的总结
数据结构与算法-五大常用算法总结(分治法,回溯法,分治限界法,贪心算法,动态规划法),算法数据结构 五大常用算法
关于分治法的算法结课论文,讲述了分治法与递归的联系与区别。分治法是解题思路,而递归是实现的方法,可用递归,也可用非递归
找第K小问题 C语言 分治法 实现的比较乱 但是算法还是很清晰的
第十讲 分治法总结.ppt 算法分析与设计
算法分析第二单元员 分治法的学习 中的经典问题3 也叫做归并排序
2.采用分治法求解最大连续子序列和问题 给定一个有n(n≥1)个整数的序列,要求求出其中最大连续子序列的和。 例如: 序列(-2,11,-4,13,-5,-2)的最大子序列和为20序列; (-6,2,4,-7,5,3,2,-1,6,...
必做:n 用分治思想设计实现二分搜索、合并排序,并且用不同数据量进行实验对比分析。 选做:阶乘(递归与分治)。
labview的子串和数值提的实现,对于学习使用labview具有极大帮助
实验1 利用减治法和分治法来处理同一个问题 一、实验目的 二、实验内容和要求 【俄式乘法函数原型及功能说明】 【核心函数实现代码及时间复杂度与空间复杂度分析】 (1)俄式乘法实现代码 (2)时间复杂度:O...
本系列实验报告涵盖了多个算法设计与分析的实验,包括动态规划、贪心算法、分治法和回溯法等算法思想的应用。实验任务多样,涉及矩阵链相乘问题、投资问题、背包问题、旅行商问题(TSP)、数字三角形、哈夫曼编码、...
使用JAVA解决残缺棋盘覆盖问题:一个n*n的棋盘上有一个缺陷点,该点不能被覆盖,剩下的格子全部用三盒板覆盖。应用的是分治法。
递归与分治实验(二)Problem A:再次Hanoi塔问题Problem B:输油管道问题Problem C:Integer FactorizationProblem D:邮局选址问题Problem E:Gray code
主要介绍了Python分治法定义与应用,较为详细的分析了Python分治法的概念、原理、用途,并结合实例总结了Python分治法的各种常见应用,需要的朋友可以参考下
本文为博主基于课堂ppt以及自行编写的代码整理的研究生《算法设计与分析》课程笔记,涉及分治算法、动态规划算法、贪心算法、回溯算法、分支限界法。总结了各类算法的思想和基本解题思路,以及对应的经典题目,适合...
汇总了计算机研究生复试有关算法分析与...12. 分治法、贪心算法与动态规划算法的差异; 13. 回溯法的基本思想; 15. 分支限界法的基本思想; 17. 简述分支限界法与回溯法的不同点; 18. 基于分治法的排序算法有哪些?
递归小结 •优点:结构清晰,可读性强,而且容易用数学归纳法来证明算法的正确性,因此它为设计算法、调试程序带来很大方便。 •缺点:递归算法的运行效率较低,无论是耗费的计算时间还是占用的存储空间都比非递归...
本文为博主基于课堂ppt以及自行编写的代码整理的研究生《算法设计与分析》课程笔记,涉及分治算法、动态规划算法、贪心算法、回溯算法、分支限界法。总结了各类算法的思想和基本解题思路,以及对应的经典题目,适合...
计算机常用算法简介、分治与递归、动态规划、贪心算法、回溯法、分限界法等等算法模型及总结
总结的关于中科大研究生课程算法设计与分析习题答案,包括分治法、动态规划、贪心算法、回溯、分支限界等章节内容