# 算法设计与分析基础

> 算法设计与分析基础

- 发布于：2020-06-18
- 更新于：2020-06-18
- 分类：学习
- 标签：other
- 原文：https://chanx.tech/blog/algorithm-design

专业课内容节选自《算法设计与分析基础》潘彦（译）

<!-- more -->



绪论：欧几里得算法的证明和实现（扩展：扩展欧几里得算法）、求最大公约数的多种算法（扩展：最小公倍数）、素数判定的多种算法、基本数据结构

算法效率分析基础：描述效率的渐进式符号、非递归和递归的效率分析

蛮力法：选择和冒泡排序、顺序查找和字符串匹配、最近对和凸包问题、穷举查找（旅行商问题、背包问题、分配问题、DFS和BFS）

减治法：插入排序、拓扑排序、生成组合对象的算法（生成排列、子集）、减常因子算法（折半查找、假币问题）、减可变规模算法：计算中值和选择问题、插值查找

分治法：合并排序、快速排序、二叉树遍历及其相关特性、大整数乘法和Strassen矩阵乘法、最近对和凸包问题

变治法：预排序、高斯消去法、AVL树四种旋转、堆排序、霍纳法则和二进制幂、问题化简（最小公倍数）

时空权衡：计数排序（比较、分布、字符串匹配：Horspool、Boyer-Moore）

动态规划：背包问题和记忆化功能、最优二叉查找树、Warshall和Floyd算法

贪婪技术：Prim算法、Kruskal算法、Dijkstra算法、哈夫曼树及其编码



部分练习题如下：

![2020061801](https://cdn.chanx.tech/image/7ep46_0.png)

![2020061802](https://cdn.chanx.tech/image/7enk4_0.png)