算法系列

以后不管干什么,都必须从宏观入手

这次算法&数据结构的学习,和我以前学习的方式不太一样了,不在是抱着一本书,从前往后看,而是立下自己要学习的目标。反过去从书中学,网上学,不在是书指导我的思维

我对于该知识学习的等级,越深入,所需时间是几何倍的增长。(所以需要自己掌握这个度)

  1. 宏观篇(有一个大体的了解,最少仅限于概念懂,最多看懂代码实现)
  2. 微观篇(不深入怎么能叫微观呢?最少有一个自己的实现,和一个完美的实现)
  3. 极致篇(多半我不会来这里,来了,就是死磕,不允许自己心中还有疑问)

眉毛胡子一把抓,是不行的,但下面这些是我必须掌握的

数据结构

线性表

  • 数组
  • 链表
    • 单链表
    • 双向链表
    • 循环链表
    • 双向循环链表
    • 静态链表
    • 顺序栈
    • 链式栈
  • 队列
    • 普通队列
    • 双端队列
    • 阻塞队列
    • 并发队列
    • 阻塞并发队列

散列表

  • 顺序散列
  • 冲突散列
    • 链表法
    • 开发寻址
    • 其它
  • 动态扩容
  • 位图

  • 二叉树
    • 平衡二叉树
    • 二叉查找树
    • 平衡二叉查找树
    • 完全二叉树
    • 满二叉树
  • 多路查找树
    • B树
    • B+树
    • 2-3树
    • 2-3-4树
    • 小顶堆
    • 大顶堆
    • 优先级队列
    • 斐波那契堆
    • 二顶堆
  • 其它
    • 树状数组
    • 线段树

  • 图的存储
    • 邻接矩阵
    • 邻接表
  • 拓扑排序
  • 最短路径
  • 关键路径
  • 最小生成树
  • 二分图
  • 最大流

算法

复杂度分析

  • 空间复杂度
  • 时间复杂度
    • 最好
    • 最坏
    • 平均
    • 均摊

基本算法思想

  • 贪心算法
  • 分治算法
  • 动态规划
  • 回溯算法
  • 枚举算法

排序

  • 时间复杂度:O(n^2)
  • 时间复杂度:O(nlogn)
  • 时间复杂度:O(n)

搜索

  • 深度优先搜索
  • 广度优先搜索
  • A*启发式搜索

查找

  • 线性表查找
  • 树结构查找
  • 散列表查找

字符串匹配

  • 朴素
  • KMP
  • Robin-Karp
  • Boyer-Moore
  • AC自动机
  • Trie
  • 后缀数组

    其它

  • 数论
  • 计算几何
  • 概率分析
  • 并查集
  • 拓扑网络
  • 矩阵运算
  • 线性规划