递归与分治
知止自律打卡-微信小程序APP
一款微信自律打卡小程序,支持自定义打卡项目、习惯记录、项目日记、专注计时与数据统计。自律打卡、学习打卡、读书打卡、健身打卡、运动打卡、减肥打卡、戒色打卡、养生打卡、戒烟、戒酒、戒熬夜等多种场景。万能打卡模板自由创建。可自定义每日打卡目标,记录习惯连续天数,可视化追踪成长进度。
了解产品详情 →
微信搜索「知止自律打卡」
1 递归与分治
1.1 递归
递归算法:直接或间接地调用自身的算法。
递归函数:用函数自身给出定义的函数。
1.2 分治法
思想:一个规模为 n 的问题,分解为 k 个规模较小的子问题,这些子问题互相独立且与原问题相同。
==二分搜索==
基本思想:
- a[0] ... a[n-1]

复杂度顺序搜索比较:

代码实现:
2 动态规划
思想:将一个规模为 n 问题分解为 k 个规模较小的子问题,但是这些子问题不独立,保存已解决的子问题的答案,而在需要时在找到求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。
基本步骤 :
(1)找出最优解的性质,并刻画其结构特征。
(2)递归地定义最优值
(3)以自底向上的方式计算最优值
(4)根据计算最优值时得到的信息,构造最优解。
最少数乘次数:最优值
最优计算次序:最优解
最优子结构性质:一定最优
3 贪心算法
- 局部最优选择
- 贪心算法
(1)贪心选择性质
(2)最优子结构性质:原问题最优解包含子问题最优解。
- 最优装载
- 活动安排问题
4 回溯法
基本步骤:
(1)定义解空间
(2)构造解空间
(3)构造解空间树
(4)搜索(深度有限)
名词解释:
(1)解空间:所有解的集合
(2)解空间树:子集树,所有接构造为一棵树
(3)死节点:2个节点都遍历了
(4)活结点:还有没有遍历的
- 批处理作业调度
- n后问题
5 分支限界法
1. 分支限界法与回溯法的不同:
(1)求解目标:回溯法的求解目标是找出解空间树中满足约束条件的所有解,而 分支限界法的求解目标是找出满足约束条件的一个解,或是满足约束条件的解中找出某种意义下的最优解。
(2)搜索方式的不同:回溯法以深度优先的方式搜索解空间树,而分支限界法则以广度有限或以最小耗费优先的方式搜索解空间树。
思想:
常以广度优先或以最小耗度(最大收益)的方式搜索问题的解空间树。
标签: