发表于 | 分类于 | 0 | 阅读次数 2654

以下内容是由 XMind 根据上述思维导图的内容自动转换而来。

数据结构和算法

Motivation

为什么学

是什么

怎么学

复杂度

大 O 复杂度表示法

  • 代码执行时间/存储空间随数据规模增长的变化趋势

时间复杂度

  • 分析方法

    • 找循环最多
    • 加法法则
    • 乘法法则

  • 常见复杂度

    • O(1)
    • O(logn)
    • O(n)
    • O(nlogn)
    • O(n^2)
    • O(2^n)
    • O(n!)
    • O(m+n)
    • O(m*n)

  • 种类

    • 最好
    • 最坏
    • 平均（使用期望值）
    • 均摊（使用摊还分析法）

空间复杂度

  • 分析方法

    • 看变量声明时分配的空间大小即可

  • 常用空间复杂度

    • O(1)
    • O(n)
    • O(n^2)

数据结构

线性表

  • 数组

    • 数组操作

      • 随机访问

        • 按下标随机访问的时间复杂度是 O(1)

      • 插入

        • 数组插入时的时间复杂度不一定是 O(n)，比如数组是无序的，只做存储集合的话，不一定要搬移一大堆数据。比如要插在第 k 个位置的话，那么可以将第 k 个数据移到最后，然后新的元素放到第 k 个位置。

      • 删除

        • 数组删除时的时间复杂度也不一定是 O(n)，比如数组不要求是连续的，那么可以采用标记删除法，也就是先将要删除的元素进行标记或记录（并不进行删除），当数组没有空间时，再执行一次总的删除操作。--- JVM 的标记垃圾回收算法

    • 深度*

      • 容器和数组

        • 存储基本类型且关注性能
        • 大小事先已知
        • 多维数组

      • 下标为什么从 0 开始

        • 从 1 开始需要做一次减法

  • 链表

    • 种类

      • 单链表
      • 循环链表
      • 双向链表
      • 双向循环链表

    • VS 数组*

      • 随机访问、插入删除的时间复杂度
      • 缓存机制
      • 扩容
      • 内存碎片

    • 代码编写

      • 留意边界条件（插入、删除、查找都需要考虑）

        • 没有结点
        • 只有一个结点
        • 两个结点
        • 头尾结点

      • 利用哨兵统一代码

      • 画图

      • 插入/删除的顺序要注意

      • 多练

    • 应用

      • LRU
      • Java 的 LinkedHashMap---双向链表
      • Linux 内核中

  • 栈

    • Motivation

      • 暴露太多接口，也需要遵守一定的最小权限原则

    • 栈的概念

      • 只在一端（栈顶）插入/删除的线性表

    • 栈的实现

      • 顺序栈
      • 链式栈

    • 栈的应用

      • 函数调用

        • 不一定要用栈来保存临时数据，只是栈比较符合这个应用场景

      • 表达式求值

      • 括号匹配

  • 队列

    • 队列的概念

      • 队头出，队尾进，先进先出的规则

    • 队列的实现

      • 顺序队列

        • 假队满

      • 链式队列

      • 循环队列

        • 队空、队满的判断，空一个位置

    • 队列的应用

      • 阻塞队列

        • 队空/队满阻塞

      • 并发队列

        • CAS 提高并发性能，不阻塞

      • 消息队列

      • FIFO 调度算法

树

  • 基本概念

    • 父节点/子节点/兄弟节点/叶子节点
    • 高度/深度/层次（深度+1）

  • 二叉树

    • 存储

      • 链式

      • 数组

        • 根节点下标为 1，左节点 2i，右节点 2i+1；适合满二叉树、完全二叉树

    • 遍历

      • 遍历方式

        • 前序
        • 中序
        • 后序

      • 实现方法

        • 递归
        • 栈
        • 莫里斯

      • 时间复杂度

        • O(n)

    • 特殊的二叉树

      • 完全二叉树

        • 叶子节点在最底下两层，最后一层的叶子节点都靠左，除最后一层之外，所有叶子节点都靠左排列

      • 满二叉树

        • 特殊的完全二叉树。叶子节点全在底层，除叶子节点之外，每个节点都有左右两个子节点。

      • 二叉查找树（二叉排序树、二叉搜索树）

        • 任何一个节点，其左子树的每个节点都要小于这个节点，而右子树的每个节点都要大于这个节点。

        • 常见操作

          • 查找

            • 最坏时间复杂度 O(n)，最好时间复杂度O(logn)

          • 插入

          • 删除

          • 最大/最小节点

          • 中序遍历得到有序序列

        • 支持重复数据的二叉查找树

          • 每个二叉树节点存储一个链表的首地址

      • 平衡二叉查找树

        • Motivation

          • 二叉查找树的查找时间复杂度不稳定，跟树的平衡有关。而插入删除操作会导致树变得不平衡，所以我们需要在插入、删除之后确保树的平衡。

        • VS 散列表

          • 散列表输出无序
          • 散列表的设计需要考虑很多，平衡二叉树只需要考虑平衡
          • 散列表由于冲突会有空间浪费
          • 散列表的查找时间复杂度虽然为 O(1)，但是查找时间不一定比 O(logn) 小，因为散列函数
          • 扩容上，散列表扩容耗时多，而且存在散列冲突，不稳定

        • AVL

          • 平衡的要求十分苛刻

        • 红黑树

          • 平衡的要求不那么十分苛刻

      • B+ 树

        • 二叉查找树演变而来，B+ 树的非叶子节点不存储数据本身，而是只作为索引；叶子节点才存储实际数据，并且把叶子节点串在一条链表上，链表上的数据从小到大有序。

堆

  • 基本概念

    • 1.完全二叉树
    • 2.节点大于等于子节点---大顶堆（反之小顶堆）

  • 堆的存储

    • 数组

  • 堆化

    • 自上而下---适合删除
    • 自下而上---适合插入

  • 堆的应用（适合于动态数据集合的场景）

    • 堆排序

      • 建堆

      • 排序

        • 取堆顶元素 ---> 堆化

    • 优先级队列

      • 合并有序小文件
      • 合并 k 个有序链表

    • 求 Top K（胜于快排）

      • Top K 大 --- 小顶堆
      • Top K 小 --- 大顶堆

    • 求中位数及各种百分位的数据

      • 维护一个大顶堆、一个小顶堆，大顶堆堆顶元素小于小顶堆堆顶元素

散列表

  • 散列函数

    • 将输入映射为数字

    • 选定原则

      • 简单
      • 随机和分布均匀

  • 散列冲突

    • 开放寻址法

      • 线性探测

        • hash(key)+1、hash(key)+2（删除过程比较特殊）

      • 二次探测

        • hash(key)+12 、hash(key)+22

      • 双重探测

        • 使用多个散列函数 hash1、hash2，hash1 冲突了则 hash2

    • 链表法

  • 装载因子

    • 填入表中的元素个数/散列表的长度

  • 扩容

    • 简单扩容
    • 高效扩容

  • [[Java 的 HashMap]]

    • 首先获取 hashcode，之后高位和低位异或，最后与 capacity - 1 相与
    • 链表法：链表和红黑树相互转换
    • 装载因子的阈值是 0.75，超过扩大两倍
    • 默认大小是 16，设置的值会变成 2^n

  • [[散列表和链表联用]]

    • LRU 链表
    • LinkedHashMap

图

  • 图的存储

    • 邻接矩阵

      • 浪费存储空间
      • 存储方式简单、直观，查找两个顶点的关系时比较高效
      • 方便矩阵运算

    • 邻接表/逆邻接表

      • 节省存储空间
      • 不方便查找（可以把链表换成红黑树、散列表等）

  • 图的常用算法

    • BFS

      • 无权重的图中，该方法是最短路径
      • 使用队列
      • 时间复杂度 O(V+E)，采用邻接表，V 是顶点数，E 是边数
      • 空间复杂度 O(V)

    • DFS

      • 回溯思想，适合用递归的方式
      • 使用栈
      • 时间复杂度 O(V+E)，采用邻接表，V 是顶点数，E 是边数
      • 空间复杂度 O(V)

常用算法

排序算法

  • 冒泡

    • 稳定、原地

  • 插入

    • 稳定、原地

  • 选择

    • 不稳定、原地

  • 归并

    • 稳定、不原地

  • 快排

    • 不稳定、原地

  • 堆

    • 不稳定、原地

  • 桶

    • 稳定、不原地

  • 计数

    • 稳定、不原地

  • 基数

    • 稳定、不原地

递归

  • 递归的三个条件

    • 问题可以分解成子问题，问题的解可以由子问题的解组成
    • 子问题和原问题的求解方法完全一样
    • 存在终止条件

  • 编写递归的技巧

    • 找出大问题分解为小问题的规律，写出递推公式；之后再确定终止条件；最后将这些翻译成代码
    • 千万不要铺开去模拟递归的过程，考虑两层即可：即假设子问题已经求解了，那么怎么把子问题的解合成大问题的解（大问题的解和子问题的解形式是一样的）

  • 弊端

    • 堆栈溢出
    • 重复计算
    • 函数调用耗时多
    • 空间复杂度高

查找算法

  • 二分查找

    • 优势

      • 在内存上更节省，跳表、散列表、二叉树都需要额外的空间
      • 适合用在查找“近似”的问题上，比如第一个大于等于、最后一个小于等于

    • 弊端

      • 依赖于数组（链表不行），因为需要随机访问
      • 针对有序数组
      • 查找数据量不能太小或太大

  • 跳表

    • 动态数据结构，在有序的链表的基础之上构建区间索引，空间复杂度是 O(n)、时间复杂度是 O(logn)

高级

索引

  • 散列表
  • 红黑树
  • B+ 树
  • 跳表
  • 位图/布隆过滤器
  • 有序数组

位图/布隆过滤器

  • 布隆过滤器其实就是在位图的基础之上使用多个哈希函数来定位一个数据是否存在。比如使用 k 个哈希函数得到 k 个值，之后将位图这 k 个位置都标上。

  • 适用场景

    • 布隆过滤器会将一个不存在的值误判为存在，但是不存在的值一定会判为不存在。所以，适合于不需要 100% 准确，允许存在小概率误判的大规模场景。

哈希算法

  • 应用场景

    • 唯一标识
    • 数据校验
    • 安全加密
    • 哈希函数
    • 数据分片（分布式）
    • 负载均衡（分布式）
    • 分布式存储（分布式）

  • 设计要点

    • 不能从哈希值反推原始数据
    • 输入数据敏感（输入数据改变，最终的哈希值就改变）
    • 冲突概率小
    • 执行效率高

  • 实例

    • MD5
    • SHA
卷死我
  • 本文作者： dawnguo
  • 本文链接： /archives/169
  • 版权声明： 本博客所有文章除特别声明外，均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处！
0%