本文主要是介绍南开大学软件学院2021年秋季学期研究生算法课程（复习）贪心分治之贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
贪心
二分查找
二分答案
二分不一定要在有序序列上进行，亦可是单调函数
砍木头
将n根长度不同木头砍成至少m段，要求砍完后每段木头的长度相等。问砍完后每段木头最长有多长？
- 暴力搜索解优化问题？貌似没什么突破口
- 优化转为判定问题？判断一个长度是否组成至少m段，很好判断，并且长度最小为1，最大为木头最大长度
- 暴力枚举长度吗？不必，随着每段长度增加，段数减少，变成找满足条件的最大值，故二分每段长度，
二分答案
将一个复杂的优化问题转化成一个可行性判定问题，本质是枚举答案判定可行，不过可行性存在单调性，可二分
若价值函数不再是单调的，而是上凸函数，能否快速找到最大值？
三分搜索（爬山法）
求一维上凸函数在
的最大值
- 取
区间的三等分点
和
黄金分割比法（0.618搜索）
一维搜索（线搜索）
- 黄金分割比法 无需求导，只需要函数值
- 割线法 需要一阶导数，快速收敛
- 牛顿法 需要二阶导数，更快收敛
最速下降法 沿梯度方向线搜索
贪心算法小结
- 难点：不计算所有子问题解的情况下，判断最优解在哪个子问题
- 特点：时间复杂度通常非常低，但正确性最难保障
- 思维特点：
- 子问题规模成倍缩小，且最优解可不算即知在哪个子问题
- 优化问题向判定问题转换是关键技巧
这篇关于南开大学软件学院2021年秋季学期研究生算法课程（复习）贪心分治之贪心的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
