算法设计与分析基础

本文最后更新于:1 个月前

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

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

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

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

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

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

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

时空权衡:计数排序(比较、分布、字符串匹配:Horspool、Boyer-Moore)

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

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

部分练习题如下:

2020061801

2020061802


算法设计与分析基础
https://www.chanx.tech/2020/88e79e65fb37/
作者
ischanx
发布于
2020年6月18日
更新于
2022年6月12日
许可协议