数据结构第二季 Day16 贪心、分治
2021-10-22 本文已影响0人
望穿秋水小作坊
一、贪心（Greedy）
1、什么是贪心策略？经典应用有哪些（至少说两个）？
-
贪心策略，也称为贪婪策略。
-
每一步都采取当前状态下最优的选择（局部最优解），从而希望推导出全局最优解。
-
贪心的应用：哈夫曼树、最小生成树（Prim、Kruskal）、最短路径算法（Dijkstra）
image.png
2、贪心策略 - 练习 1 - 最佳装载问题（加勒比海盗）？
- 贪心策略：每一次都优先选择重量最小的古董
image.png
3、 贪心策略 - 练习 2 - 零钱兑换？
- 贪心策略：每一次都优先选择面值最大的硬币
image.png
4、上述零钱兑换算出来的一定是最优解吗？（贪心存在的问题？）
- 不一定是最优解：贪心算法只求局部最优，不能保证全局最优。
image.png
5、 总结贪心算法的问题？
image.png
6、 贪心策略 - 练习 3 - 零一背包问题？
image.png
image.png
image.png
7、 贪心策略作业
image.png
二、分治（Divide And Conquer）
1、分治的核心思想是什么？在排序算法中典型应用是哪两个？
- 分治：也就是
分而治之 - 典型：归并排序、快速排序
image.png
2、为什么分治之后，会优化提升归并排序、快速排序的时间复杂度？
image.png
- 在 day16 的1：34：00 可以多听几遍
3、分治策略的主定理？
image.png
4、理解什么是子序列？什么是连续子序列？（这些概念在算法中经常遇到）
image.png
image.png
5、分治 - 练习1 - 最大连续子序列和
image.png
6、分治-练习 1-解法 1 暴力出奇迹
- 感觉核心点在于 - 分成了 begin 和 end 两个指针，让问题非常清晰的呈现出来
image.png
7、分治-练习 1-解法 1 暴力法优化
image.png
8、使用分治的解法？
image.png
image.png
