算法设计与分析核心要点

算法设计与分析核心要点其中包含了几大基本算法设计思想，可以让我们对算法有一个清晰地整体认识，有助于我们更好的理解算法以及应试。

算法设计与分析核心要点

• 4.分治
  • 快排
  • 合并排序
  • 比较排序下界
  • 堆定义与构建修复
  • 堆排序
  • 线性时间选择（注意复杂度）
  • 折半查找
  • 二插搜索树
  • 红黑树概念及性质
• 5.贪心
  • Prim算法及实现
  • Kruskal算法及实现
  • 并查集的使用
  • MCE框架
  • Dijkstra算法
  • BestFS框架
  • 相容调度与Huffman编码
• 6.动态规划
  • F-W的算法思想
  • 动态规划的几个例子都看看
  • 动态规划的要素
  • 状态转移方程
• 7.计算复杂性理论初步
  • 问题规约
  • P/NP/NP完全问题定义
  • NP完全性简单证明
• 注：这本书主要在理解，多看几次各种算法思想，代码着重在DFS/BFS/动归那里，多次看书就好。
• 3.朴素遍历
  • DFS框架
    • 遍历树概念
    • 活动区间
    • 白色路径定理
    • 应用
      • 拓扑排序
      • 关键路径
      • 找强连通片
  • BFS框架
    • 注意各定理引理
    • 部分应用
    • 队列实现
• 2.算法审视数学概念
  • 渐进增长率
  • 分治思想
  • 递归树
  • Master定理
• 1.计算模型
  • RAM模型
  • 算法时间复杂度/空间复杂度