201820192《算法设计与分析A》复习提纲 总.docx

复习提纲 第1章： 算法的重要问题类型 第2章 算法的分析框架，包括输入规模的度量、运行时间的度量、增长次数、最优最差及平均效率等知识点。 增长次数、渐进符号和基本效率类型、分析算法的执行次数，包括递归与非递归算法的分析方法，反向替换法等。 第3章 选择排序、字符串匹配、穷举查找：包括背包问题和分配问题； 最近对和凸包问题的蛮力算法、深度优先查找和广度优先查找 第4章 插入排序、拓扑排序、计算中值和选择问题 第5章 合并排序、快速排序、大整数乘法 第6章 平衡查找树、堆的概念、堆排序 第8章 最优二叉查找树、Warshall算法 第9章 Prim算法、Kruskal算法，注意算法和构造最小生