《算法导论》学习笔记

Date: 2022.06

数据结构和算法是编程的灵魂。

• 函数的增长

  • 渐进记号

• 复杂度分析

  • 摊还分析
    • 核算法
    • 势能法

• 分治策略

  • 对递归式的求解
    • 主定理

• 贪心算法

  • 霍夫曼编码
  • Dijkstra 算法
  • 最小生成树的 Prim 算法和 Kruskal 算法
  • 最佳优先搜索（BFS）
  • A*寻路算法（启发式的贪心算法）
  • 拟阵理论来证明贪心算法能找到最佳解

• 动态规划

  • 动态规划问题的特征
  • 最长公共子序列问题（LCS）

• 排序

  • 冒泡排序
  • 快速排序
    • pivot
    • 快速排序的优化
  • 归并排序
  • 堆排序
  • 桶排序
  • 计数排序
  • 基数排序

• 中位数和顺序统计量

• 散列表

  • 散列函数
  • 解决冲突

• 平衡树

  • B 树
  • 红黑树
  • 斐波那契堆

• van Emde Boas 树

• 用于不相交集合的数据结构

• 图算法

  • 遍历
    • 深度优先遍历
    • 广度优先遍历
  • 拓扑排序算法
  • 最小生成树算法
    • Prim 算法
    • Kruskal 算法
  • 最短路径问题
    • Dijkstra 算法（单源最短路径算法）
  • 所有结对点的最短路径问题
  • 寻路算法
    • 广度优先搜索
    • Dijkstra 算法
    • 贪婪最佳优先搜索
    • A*算法
    • B*算法
  • 最大流问题

• 多线程算法

  • 多线程执行模型
  • 性能分析
  • 多线程矩阵乘法
  • 多线程归并排序
  • 为多线程算法设计的硬件

• 线性规划

  • 把一个问题转化为线性规划问题
  • 线性规划的求解原理

• 数论算法

  • 加密

• 字符串匹配算法

  • 朴素算法
  • Robin-Karp 算法
  • 有限自动机算法
  • KMP 算法

• NP 完全性

• 近似算法