您现在的位置是:首页 >学无止境 >【算法导论】算法分析与设计_理论知识点(可用于备考)网站首页学无止境

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

宛如近在咫尺 2023-07-14 00:00:02
简介【算法导论】算法分析与设计_理论知识点(可用于备考)

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

  1. 快速排序、堆排序是原地排序、不稳定排序。
  2. 归并排序和堆排序的最坏情况是 O ( n l o g n ) O(nlogn) O(nlogn)
  3. 快速排序最坏情况是 O ( n 2 ) O(n^2) O(n2)
  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 ) O(n) 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 ) O(n^3) O(n3)(三个嵌套For循环),其实现步骤见博客
  35. 贝尔曼-福特算法(Bellman-Ford),单源最短路径的一种解决方法,相比Dijkstra来说Bellman-Ford可以用于处理负权并判断负环是否存在,但时间复杂度较高 O ( V E ) O(VE) O(VE),V点数,E边数。
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。