您现在的位置是:首页 >学无止境 >【算法导论】算法分析与设计_理论知识点(可用于备考)网站首页学无止境
【算法导论】算法分析与设计_理论知识点(可用于备考)
简介【算法导论】算法分析与设计_理论知识点(可用于备考)
前言:汇总计算机算法领域需要了解的理论知识点,可用于备考算法期末考试、自查等。
- 快速排序、堆排序是原地排序、不稳定排序。
- 归并排序和堆排序的最坏情况是 O ( n l o g n ) O(nlogn) O(nlogn)。
- 快速排序最坏情况是 O ( n 2 ) O(n^2) O(n2)。
- 计数排序和基数排序都需要额外的空间,因此不是原地排序。
- 数组{1,2,3}是
大顶堆小顶堆。 - 计数排序不是一个比较排序。
- 若一个问题不满足最优子结构性质,
仍然可以不可以用贪心算法求最优。 - 最优子结构:一个问题的解包含子问题的解。
- 什么时候可以用贪心算法:两个条件同时满足 ①最优子结构:一个问题的解包含子问题的解;②贪心选择性质:我们可以通过构造局部最优解来求出全局最优解 。
- 哈夫曼编码(
Huffman Coding
)是后缀码前缀码,该算法可以用于压缩数据。 - 具有相同带权节点的哈夫曼树不唯一。
- 回溯法是深度优先搜索(
DFS
)的搜索次序。 - 算法导论中提到的限界函数(
Bound Function
)是指杀死没必要展开的节点(剪枝)。 - 不可判定问题(
undecidable problem
):通用的求解算法不存在,不存在一个算法在有穷时间内给出“是”或“否”的答案。 - NP(
Nondeterministic Polynomially,非确定性多项式
)问题是指一个问题不能确定是否在多项式时间内找到答案,但可以在多项式时间内验证答案是否正确。常见的NP问题如TSP旅行商问题、图着色问题。 - P问题则是可以用一个确定的算法在多项式时间内判定和解出答案。
- NP完全问题(
NP Complete,NPC
):只要解决了这个问题,那么所有的NP问题都可以被解决。 - 如果一个NPC问题能在多项式时间内被解决,那么
NP=P
. - 使用分治法求解问题时、其子问题不能够重复、子问题的解可以合并、原问题和子问题使用相同的方法求解。
- 计数排序、基数排序、桶排序都是在线性时间内完成的排序,都是 O ( n ) O(n) O(n)。
- 回溯法的求解目标是找出解空间中满足约束条件的所有解(DFS)。
- 分支限界法(
Branch and Bound Method
)的求解目标是尽快找出满足约束条件的一个解(BFS)。 - 分支限界法中,每一个活结点只有一次机会成为扩展结点,一旦活结点成为了扩展结点,就一次性产生其所有的儿子结点。
- 备忘录(
Memoization
)主要用于动态规划。 - 采用最大效益优先搜索的算法是
回溯法分支限界法。 - 分支限界:广度优先&最小代价优先。
- 经典问题分数背包问题中的贪心:选择性价比最好的。
- 经典问题 活动选择问题 中的贪心:选择结束时间最早的。
Huffman
编码中的贪心:选择两个最小的进行合并。- 单源最短路径中的迪杰斯特拉算法(
Dijkstra
)本质是一种贪心算法。 - 动态规划问题需具备的特征:①最优子结构;②有重叠子问题:不同的子问题有公共的子问题;③无后效性:当前的若干状态一旦确定,此后的推导演变过程只与这些状态的值有关,与这些值的求解历程无关。
- 在递归法(自顶向下)求解动动态规划问题中如何解决重叠子问题:使用备忘录,将已解决的子问题记录下来,后续遇到无需再次求解,直接取出备忘录中的答案。
- 分治法的步骤:①分:分解成子问题;②治:解决子问题;③合:合并子问题。
- 弗洛伊德(
Floyd
)算法:多源最短路径的一种解决方法,可解决任意两点之间的最短路径,能处理有向图和负权,时间复杂度为 O ( n 3 ) O(n^3) O(n3)(三个嵌套For循环),其实现步骤见博客。 - 贝尔曼-福特算法(
Bellman-Ford
),单源最短路径的一种解决方法,相比Dijkstra
来说Bellman-Ford
可以用于处理负权并判断负环是否存在,但时间复杂度较高 O ( V E ) O(VE) O(VE),V点数,E边数。
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。