导论分治排序堆排序优先队列快速排序决策树模型线性排序动态规划装配线调度问题矩阵链乘问题备忘录模式最长公共子序列贪心算法活动选择霍夫曼编码部分背包图算法单源点最短路径任意节点对间最短路径回溯法N-皇后问题分支限界NP问题考试题型
导论
- 循环不变式（了解概念）
- 插入排序算法的时间复杂度（三种情况下）、稳定性、空间复杂度
- 原地排序
分治
- 分、治、合并
- 归并排序
- 最大子数组问题
- 矩阵相乘（Strassen算法，了解）
- 分析分治算法（递归算法）的时间复杂度
- 渐近分析
- 表示复杂度的三个符号
- 递归式的三种求解方法
- 猜测法
- 递归树法
- 主定理法（不要直接给答案，要有过程）
排序
堆排序
- 堆
- MAX-HEAPIFY
- BUILD-MAX-HEAP
- HEAPSORT
优先队列
- MAXIMUM
- EXTRACT-MAX
- INCREASE-KEY
- INSERT
快速排序
- 分治思想
- PARTITON
- 时间复杂度
- 不稳定
- 随机化的快速排序
决策树模型
- 任意基于比较的排序算法
线性排序
- 桶排序
- 基数排序
- 数排序
动态规划
- 什么是最优解？
- 什么是最优解的值？
- 四个步骤
- 递归设计
- 自底向上设计
装配线调度问题
- 递推式
矩阵链乘问题
- 递推式
备忘录模式
最长公共子序列
贪心算法
活动选择
霍夫曼编码
部分背包
图算法
- 据说考试占比提高
单源点最短路径
- 迪杰斯特拉算法
- 贝尔曼-福德算法
任意节点对间最短路径
- All-pairs shortest path
- Floyd-Warshall算法
- Johnson算法
回溯法
- 深度优先
N-皇后问题
- 限界函数
分支限界
- 广度优先
NP问题
- 计算机不可解问题
- P、EXP、NP、NP-Complete的概念
- 哪些问题是计算结可解的
- 计算机可解的问题里，哪些是简单的，哪些是复杂的
考试题型
