高级算法设计与分析(九) -- 总结

2023-12-20 15:48:17

系列文章目录

高级算法设计与分析(一) -- 算法引论

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

高级算法设计与分析(三) -- 动态规划

未完待续【

高级算法设计与分析(四) -- 贪心算法

高级算法设计与分析(五) -- 回溯法

高级算法设计与分析(六) -- 分支限界法

高级算法设计与分析(七) -- 概率算法

高级算法设计与分析(八) -- NP完全性理论

高级算法设计与分析(九) -- 总结


目录

系列文章目录

一、算法引论

二、递归与分治策略

1、分治法

2、二分法

3、大整数的乘法

4、棋盘覆盖

5、合并排序

6、循环日程表

三、动态规划

1、矩阵连乘问题

2、最长公共子序列

四、贪心算法

1、活动安排问题

2、贪心算法

3、哈夫曼编码

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

5、最小生成树

5.1、普里姆(Prim)算法

5.2、克鲁斯卡尔(Kruskal)算法

五、回溯法

1、n皇后问题

2、图的m着色问题

六、分支限界法

1、分支限界法

2、单源最短路径问题

七、概率算法

八、NP完全性理论

资料


前言

tips:鉴于本人写字如画符,就不出视频教程了,如实在有需要,请在文章下方留言。当然,文章有任何问题,也请留言,谢谢!

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

本文章为简要总结,思维导图放在文章最下面,请自行获取。


一、算法引论

?

递归问题求时间复杂度

?

二、递归与分治策略

1、分治法

累加函数时间复杂度

2、二分法

时间复杂度o(log n)

3、大整数的乘法

?

?

4、棋盘覆盖

?

1、将2^k*2^k棋盘分割为4个2^(k-1)*2^(k-1)棋盘
2、特殊方格在其中一个区域中,将其他三个无特殊方格的区域用一个L形骨牌覆盖在汇合处。

5、合并排序

时间复杂度:?

6、循环日程表

?

?

三、动态规划

1、矩阵连乘问题

?

?

?

?

2、最长公共子序列

?

最优子结构指的是,问题的最优解包含子问题的最优解。
反过来说就是,我们可以通过子问题的最优解,推导出问题的最优解。

?

?

?

?

?

四、贪心算法

1、活动安排问题

?

?

?

?

?

2、贪心算法

?

自顶向下与自底向上

?

3、哈夫曼编码

?

?

?

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

?

5、最小生成树

5.1、普里姆(Prim)算法

?

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

5.2、克鲁斯卡尔(Kruskal)算法

?

时间复杂度:o(|E|log2|E|)

比较:

?

五、回溯法

1、n皇后问题

4皇后2个解

?

5皇后10个解

?

6皇后4个解

?

?

?

2、图的m着色问题

?

?

六、分支限界法

1、分支限界法

?

?

2、单源最短路径问题

队列法分支限界求解

?

?

七、概率算法

随机数

数值概率算法

Las Vegas算法

八、NP完全性理论

计算模型

P类与NP类问题

NP完全问题

一些典型的NP完全问题


资料

高级算法设计与分析-思维导图

高级算法设计与分析-考试一张纸总结

文章来源:https://blog.csdn.net/zqx1473/article/details/135107106
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。