算法设计与分析总结

写在前面（更新中）

• 这个系列的内容主要参考了《算法导论（第三版）》、哈工大算法设计与分析课程的内容
• 主要以理解算法思想、如何设计算法、分析算法为核心，着重点不在算法的实现
• 主要目的为个人的总结学习，不足之处还望指正

目录

• 算法设计的数学基础

1. 复杂性函数的阶

2. 递归方程的求解

                             （1）代入法

                             （2）master定理

• 分治法

                                大整数乘法

矩阵乘法的Strassen算法

中位数与顺序统计量

最邻近点对问题 

•  动态规划

编号动态规划问题

划分动态规划问题

数轴动态规划问题  

前缀动态规划问题

• 贪心法

贪心算法介绍 （通过最大相容活动引入）

贪心法--最小生成树问题  

• 平摊分析

平摊分析--聚集法 

平摊分析--会计法  

平摊分析--势能法  

平摊分析的应用  （动态表、双端队列、二项队列、斐波那契堆）

• 图论算法（难） 

1. 1. 1. 图论的常用算法
      2. 网络流问题：网络流算法（Ford-fulkerson方法）
      3. 匹配问题：最大二分匹配  
      4. 搜索问题：

图的搜索策略（算法思想介绍）

分支界限法的应用 

A*算法   

•  图论算法小结 
• 字符串算法

字符串匹配算法 

查找字符串的数据结构