【算法导论】算法分析与设计_理论知识点（可用于备考）

前言：汇总计算机算法领域需要了解的理论知识点，可用于备考算法期末考试、自查等。

1. 快速排序、堆排序是原地排序、不稳定排序。
2. 归并排序和堆排序的最坏情况是$O(nlogn)$。
3. 快速排序最坏情况是$O(n^2)$。
4. 计数排序和基数排序都需要额外的空间，因此不是原地排序。
5. 数组{1,2,3}是大顶堆 小顶堆。
6. 计数排序不是一个比较排序。
7. 若一个问题不满足最优子结构性质，仍然可以 不可以用贪心算法求最优。
8. 最优子结构：一个问题的解包含子问题的解。
9. 什么时候可以用贪心算法：两个条件同时满足 ①最优子结构：一个问题的解包含子问题的解；②贪心选择性质：我们可以通过构造局部最优解来求出全局最优解 。
10. 哈夫曼编码（Huffman Coding）是后缀码 前缀码，该算法可以用于压缩数据。
11. 具有相同带权节点的哈夫曼树不唯一。
12. 回溯法是深度优先搜索（DFS）的搜索次序。
13. 算法导论中提到的限界函数（Bound Function）是指杀死没必要展开的节点（剪枝）。
14. 不可判定问题（undecidable problem）：通用的求解算法不存在，不存在一个算法在有穷时间内给出“是”或“否”的答案。
15. NP(Nondeterministic Polynomially，非确定性多项式)问题是指一个问题不能确定是否在多项式时间内找到答案，但可以在多项式时间内验证答案是否正确。常见的NP问题如TSP旅行商问题、图着色问题。
16. P问题则是可以用一个确定的算法在多项式时间内判定和解出答案。
17. NP完全问题（NP Complete，NPC）:只要解决了这个问题，那么所有的NP问题都可以被解决。
18. 如果一个NPC问题能在多项式时间内被解决，那么NP=P.
19. 使用分治法求解问题时、其子问题不能够重复、子问题的解可以合并、原问题和子问题使用相同的方法求解。
20. 计数排序、基数排序、桶排序都是在线性时间内完成的排序，都是$O(n)$。
21. 回溯法的求解目标是找出解空间中满足约束条件的所有解（DFS）。
22. 分支限界法（Branch and Bound Method）的求解目标是尽快找出满足约束条件的一个解（BFS）。
23. 分支限界法中，每一个活结点只有一次机会成为扩展结点，一旦活结点成为了扩展结点，就一次性产生其所有的儿子结点。
24. 备忘录（Memoization）主要用于动态规划。
25. 采用最大效益优先搜索的算法是回溯法 分支限界法。
26. 分支限界：广度优先&最小代价优先。
27. 经典问题分数背包问题中的贪心：选择性价比最好的。
28. 经典问题 活动选择问题 中的贪心：选择结束时间最早的。
29. Huffman编码中的贪心：选择两个最小的进行合并。
30. 单源最短路径中的迪杰斯特拉算法（Dijkstra）本质是一种贪心算法。
31. 动态规划问题需具备的特征：①最优子结构；②有重叠子问题：不同的子问题有公共的子问题；③无后效性：当前的若干状态一旦确定，此后的推导演变过程只与这些状态的值有关，与这些值的求解历程无关。
32. 在递归法（自顶向下）求解动动态规划问题中如何解决重叠子问题：使用备忘录，将已解决的子问题记录下来，后续遇到无需再次求解，直接取出备忘录中的答案。
33. 分治法的步骤：①分：分解成子问题；②治：解决子问题；③合：合并子问题。
34. 弗洛伊德（Floyd）算法：多源最短路径的一种解决方法，可解决任意两点之间的最短路径，能处理有向图和负权，时间复杂度为$O(n^3)$（三个嵌套For循环）,其实现步骤见博客。
35. 贝尔曼-福特算法（Bellman-Ford），单源最短路径的一种解决方法，相比Dijkstra来说Bellman-Ford可以用于处理负权并判断负环是否存在，但时间复杂度较高$O(VE)$，V点数，E边数。