高级算法设计与分析（八） -- 总结
系列文章目录
目录
前言
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完全问题