高级算法设计与分析（四） -- 贪心算法

系列文章目录

高级算法设计与分析（一） -- 算法引论

高级算法设计与分析（二） -- 递归与分治策略

高级算法设计与分析（三） -- 动态规划

高级算法设计与分析（四） -- 贪心算法

高级算法设计与分析（五） -- 回溯法

高级算法设计与分析（六） -- 分支限界法

高级算法设计与分析（七） -- 概率算法和NP完全性理论

高级算法设计与分析（八） -- 总结

---

目录

系列文章目录

前言

一、贪心算法的基本思想

二、活动安排问题

三、贪心算法的基本要素

四、哈夫曼编码

五、单源最短路径-Dijkstra算法

六、最小生成树

1、基础概念与问题

2、prim算法（普里姆算法）

3、kruskai算法（克鲁斯卡尔算法）

习题

---

前言

tips：这里只是总结，不是教程哈。鉴于本人写字如画符，就不出视频教程了，如实在有需要，请在文章下方留言。当然，文章有任何问题，也请留言，谢谢！

这个系列用另一种形式，把习题放在最下面，看看好用不。

本系列文章最后一文会进行简要全部总结，以及思维导图放在最后一篇文章最下面，请自行获取。

---

一、贪心算法的基本思想

50，20，0.2，0.1
3*5

二、活动安排问题

1、问题描述

给定一组活动，每个活动都有一个开始时间和结束时间，目标是安排出一个最大数量的相互兼容的活动集合，即这些活动之间不会相互冲突。

2、例子

3、步骤：

因为是按照结束时间的非减排序的，选择第一个后（红1），把开始时间在这个活动结束时间之前的都排除（红叉），然后继续选择未排除的结束时间最早的一个（绿2），把开始时间在这个活动结束时间之前的都排除（绿叉），以此类推……

4、算法正确性证明：

另一种表述，看你们能接收那种

三、贪心算法的基本要素

1、贪心选择性质、最优子结构

***自顶向下和自底向上

2、证明方法

4、贪心算法的适用范围

5、背包问题和0-1背包问题

四、哈夫曼编码

复杂度

五、单源最短路径-Dijkstra算法

1、问题描述

有向图

2、算法的基本思想

3、将算法用程序描述

复杂度分析：时间复杂度：o(|V|^2)

4、算法正确性证明

六、最小生成树

1、基础概念与问题

2、prim算法（普里姆算法）

2.1、直接算法实现

2.2、prim算法实现

时间复杂度：o(|V|^2)

3、kruskai算法（克鲁斯卡尔算法）

---

习题

topic1：

topic2：

topic3：

topic4：

topic5：

topic5:

topic6: