Skip to main content

算法导论导读

如果你正在通过阅读《算法导论》来学习算法的话，那么可以根据本文的导读进行复习和准备

第一章​

  • 什么是算法
  • 算法与数据结构的关系
  • 算法能解决什么问题？不能解决什么问题？
  • 什么是 NP 完全问题？请列举 Leetcode 上面几个 NP 完全问题

第二章​

  • 学习阅读伪代码 (pseudocode)
  • 什么是循环不变式 (loop invariant)，如何使用它证明算法的正确性？尝试使用循环不变式证明以下代码的算法正确性：
  • 什么是算法时间复杂度分析？
  • 插入排序的时间复杂度分析
  • 最好情况，最坏情况以及平均情况分析，尝试分析题目的最好，最好以及平均情况：
  • 什么是分治 (divide and conquer)？归并排序算法的时间复杂度分析
  • 什么是递归树，什么类型的题目适合使用递归树分析？尝试使用递归树分析题目的时间复杂度

第三章（学习 3.1 即可）​

  • O, Ω, Θ 的区别，一般来说我们只需要关注 Big O

第四章（忽略 4.2）​

  • 什么是递归？递归的步骤是怎样的？
  • 如何使用递归树 (recursion tree) 以及主定理 (master theory)计算时间复杂度

第五章（轻度阅读）​

第六章（轻度阅读）​

  • 什么是堆 (heap)，最大堆和最小堆的区别
  • 建堆的时间复杂度是多少
  • 堆的使用场景

第七章（轻度阅读）​

  • 快速排序 (quick sort) 的原理
  • 快速排序的性能分析

第八章​

  • 了解计数排序 (counting sort) 的实现以及原理
  • 了解桶排序 (bucket sort) 的实现以及原理
  • 什么数据规模适合哪种排序算法，尝试完成以下题目：

第九章​

  • 什么是顺序统计量
  • 如何高效找到最大值与最小值
  • 学习以及掌握快速选择 (quick select) 算法

第十章​

  • 列出你知道的所有动态集合
  • 了解栈 (stack) 和队列 (queue) 的实现方式
  • 了解链表 (linked list) 的类型以及实现方式
  • 了解什么是哨兵 (sentinel)
  • 了解什么是指针 (pointer)
  • 了解二叉树 (binary tree) 的表达方式

第十一章（轻度阅读）​

  • 哈希表 (hash table) 增删改查操作的时间复杂度
  • 哈希表解决冲突的两种方法，开放寻址法 (open address) 以及链表法

第十二章​

第十三章（轻度阅读）​

  • 红黑树 (red black tree) 的使用场景
  • 红黑树常见操作的时间复杂度

第十四章​

第十五章​

  • 动态规划 (dynamic programming) 通常求解哪一类的问题？
  • 动态规划的四个常规步骤，尝试完成以下题目的过程中，列出并且完成四个步骤
  • top-down whth memoization（带备忘的自顶向下法，通常是递归来实现）以及bottom-up method（自底向上法）的区别以及实现方式，尝试用两种方式完成以下题目：
  • 什么是子问题图，动态规划与拓扑排序的关系

第十六章​

  • 贪心算法 (greedy) 与动态规划的关系，什么时候使用其中一种?
  • 尝试证明题目贪心解法的正确性

第十七章（学习 17.1 即可）​

  • 了解聚合分析 (aggregate analysis)，尝试分析以下题目的时间复杂度，并阅读国区官方题解

第十八章（学习 18.1 即可）​

  • 了解 B 树的原理以及使用场景

第二十一章​

  • 了解不相交集合 (disjoint set) 的表达方式
  • 了解不相交集合的使用场景以及基础原理
  • 了解实现的两种优化方案，并使用自己常用的语言进行实现以及解答以下题目：

第二十二章​

  • 如何使用邻接链表与邻接矩阵表示图，它们的优缺点
  • 什么是有向图的转置
  • BFS 使用了三种颜色对节点进行染色，试讲出每种颜色节点的含义
  • BFS 的队列的作用是什么？存储的是什么颜色的节点？
  • 如何用 BFS 求节点与节点之间的最短路径
  • DFS 使用了三种颜色对节点进行染色，试讲出每种颜色节点的含义
  • 了解 DFS 节点的发现时间与完成时间，学习它们的括号化结构 (parenthesis structrue) 性质
  • 学习并且实现拓扑排序，完成以下题目：

第二十四章​

  • 了解最短路径问题的几个变体
    • 单目的地最短路径问题
    • 单结点对最短路径问题
    • 所有结点对最短路径问题
  • 了解负权重，环路等概念
  • 学习什么是松弛操作，理解松弛操作的正确性
  • 学习 Bellman-Ford 算法，有向无环图的单源最短路径问题，Dijkstra 算法，回答以下内容：
    • 每种算法的适用场景，是否适用于负权重或者有环图
    • 每种算法的时空复杂度分析

第三十一章（轻度阅读）​

  • 了解什么是素数，最大公约数
  • 了解欧几里得算法

第三十二章（轻度阅读）​

  • 了解字符串匹配的三种算法，朴素字符串匹配算法，Rabin-Karp 算法，KMP 算法并尝试解答以下题目：
  • 了解欧几里得算法

第三十三章（轻度阅读）​

  • 了解什么是向量
  • 学习如何确定连续险段是向左转还是右转，判断两条线段是否相交，确定任意一对线段是否相交