Writings

A place to place some writings

《算法导论》学习笔记

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

  • 函数的增长

    • 渐进记号
  • 复杂度分析

    • 摊还分析
      • 核算法
      • 势能法
  • 分治策略

    • 对递归式的求解
      • 主定理
  • 贪心算法

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

    • 动态规划问题的特征
    • 最长公共子序列问题(LCS)
  • 排序

    • 冒泡排序
    • 快速排序
      • pivot
      • 快速排序的优化
    • 归并排序
    • 堆排序
    • 桶排序
    • 计数排序
    • 基数排序
  • 中位数和顺序统计量

  • 散列表

    • 散列函数
    • 解决冲突
  • 平衡树

    • B 树
    • 红黑树
    • 斐波那契堆
  • van Emde Boas 树

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

  • 图算法

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

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

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

    • 加密
  • 字符串匹配算法

    • 朴素算法
    • Robin-Karp 算法
    • 有限自动机算法
    • KMP 算法
  • NP 完全性

  • 近似算法