算法的复杂度

时间复杂度

  • 常数O(1) - 哈希桶/数组随机寻址
  • 线性O(n) - 遍历
  • 对数O(logn) - 二分查找/二叉树
  • O(n*logn) - 基于比较的排序算法的下界
  • 平方O(n^2) - 冒泡排序

基本的数据结构 — 数组

  • 随机访问
    • 寻址操作O(1)： addr = start_addr + type_size * i
  • 插入、删除
    • O(n)
  • 查找
    • 无序：O(n)
    • 有序：O(logn)（二分查找）
  • 要求：手写二分查找

基本数据结构 — 链表

  • 寻址 O(n)
  • 插入/删除 O(1)
  • 查找 O(n)
  • 要求：
    • 手写翻转链表
    • 判断链表是否成环

基本数据结构 — 栈、队列

Stack

  • FILO（First In Last Out）
  • JDK Stack类，优先使用双端队列 Deque
  • 应用：方法栈

  • 要求

    • 手写栈的实现

      Queue

  • FIFO

  • 应用：线程池
  • 要求
    • 手写队列的实现

基本数据结构 — 哈希表

  • 查找/插入/删除都是O(1)
  • 哈希算法与碰撞
  • 哈希桶的内部实现
  • 哈希桶碰撞的解决
    • 64位是有限的，对象是无穷多的，一定会有哈希碰撞
    • 链表
    • Java8 超过阈值8会转红黑树