ALGORITHMS · 数据结构 / 算法分析
算法与数据结构速查
一表梳理 11 种常用数据结构的特性与复杂度，以及 9 个必会经典算法的核心思想与时间成本，面试复习与日常编码随查随用。
11数据结构
9经典算法
57速查条目
📖 速查表
点击展开各小节
📊 数据结构
| 结构 | 说明 | 时间复杂度（平均） | 典型应用 |
|---|---|---|---|
| Array 数组 | 连续内存空间存储相同类型元素，支持随机访问 | O(1) 读 / O(n) 插入删除 | ArrayList、数据缓冲区、矩阵运算 |
| Linked List 链表 | 通过指针链接的节点序列，插入删除快，不支持随机访问 | O(n) 读 / O(1) 插入删除 | LinkedList、LRU Cache、区块链 |
| Stack 栈 | 后进先出（LIFO）结构，只能在栈顶操作 | O(1) push/pop | 函数调用栈、表达式求值、括号匹配、浏览器的前进后退 |
| Queue 队列 | 先进先出（FIFO）结构，队尾入队、队首出队 | O(1) enqueue/dequeue | 消息队列、BFS 广度优先搜索、线程池任务队列 |
| Hash Table 哈希表 | 通过哈希函数将键映射到存储位置，实现 O(1) 查找 | O(1) 平均 / O(n) 最坏 | HashMap、HashSet、缓存系统、数据库索引 |
| Tree 树 | 分层结构，每个节点有零个或多个子节点，根节点唯一 | 视具体类型而定 | 文件系统、DOM 树、组织架构、路由表 |
| Binary Search Tree 二叉搜索树 | 左子树所有节点 < 根节点 < 右子树所有节点，支持高效查找 | O(log n) 平均 / O(n) 退化为链表 | TreeSet、TreeMap、数据库索引的底层结构 |
| Heap 堆 | 完全二叉树，最大堆的父节点 ≥ 子节点，最小堆相反 | O(log n) 插入/删除 / O(1) 取最值 | 优先队列（PriorityQueue）、Top K 问题、堆排序 |
| Graph 图 | 由顶点和边组成，分有向图/无向图、加权图/无权图 | O(V+E) 遍历 | 社交网络、地图导航（Dijkstra）、依赖分析 |
| Trie 前缀树 | 字符串查找树，利用公共前缀节省空间，支持前缀匹配 | O(m) m 为字符串长度 | 自动补全、拼写检查、IP 路由前缀匹配 |
| Skip List 跳表 | 多层链表的概率性数据结构，支持 O(log n) 查找 | O(log n) 平均 | Redis 的 ZSET 有序集合底层实现 |
⚡ 算法速查
说复杂度务必带上前提：平均还是最坏、是否有序、边权是否非负——面试官追问的往往就是这个前提。
| 算法 | 类别 | 时间复杂度 | 说明 |
|---|---|---|---|
| Bubble Sort 冒泡排序 | 排序 | O(n²) / O(n) 优化后 | 相邻元素两两比较，大的往后冒。稳定排序，适合小数据量或基本有序的数据 |
| Quick Sort 快速排序 | 排序 | O(n log n) 平均 / O(n²) 最坏 | 选取枢轴，分区后递归排序。大多数语言排序函数的默认实现 |
| Merge Sort 归并排序 | 排序 | O(n log n) 所有情况 | 分治思想，先将数组递归分成两半，再合并有序子数组。稳定排序，额外 O(n) 空间 |
| Heap Sort 堆排序 | 排序 | O(n log n) | 利用堆结构（最大堆）进行排序，先建堆再反复取出堆顶。不稳定排序 |
| Binary Search 二分查找 | 搜索 | O(log n) | 在有序数组中通过不断折半缩小查找范围。前提是数组已排序 |
| BFS 广度优先搜索 | 图遍历 | O(V + E) | 使用队列逐层遍历，先访问离起点最近的点。适合求最短路径（无权图） |
| DFS 深度优先搜索 | 图遍历 | O(V + E) | 使用栈（递归或显式）深入一条路径到底再回溯。适合遍历所有解空间 |
| Dijkstra 最短路径 | 图算法 | O(V²) / O(E log V) 堆优化 | 计算带权重图中从源点到所有节点的最短路径。要求边权非负 |
| DP 动态规划 | 优化方法 | 视问题而定 | 将复杂问题分解为重叠子问题，通过存储中间结果避免重复计算。经典问题：背包、LCS、LIS |
📋 复杂度总表
| 结构 | 访问 | 查找 | 插入 / 删除 |
|---|---|---|---|
| Array 数组 | O(1) 下标随机读 | O(n) 无序 / O(log n) 有序二分 | O(n) 需搬移元素 |
| Linked List 链表 | O(n) 需从头遍历 | O(n) | O(1) 已知位置时 |
| Stack / Queue 栈与队列 | O(1) 仅端点（栈顶/队首） | O(n) | O(1) 限定端点操作 |
| Hash Table 哈希表 | 不适用（无序） | O(1) 平均 / O(n) 最坏 | O(1) 平均 |
| BST 二叉搜索树 | 按序遍历 O(n) | O(log n) 平均 / O(n) 退化 | O(log n) 平均 / O(n) 退化 |
| Heap 堆 | O(1) 仅堆顶 | O(n) 任意元素 | O(log n) 插入与下沉 |
| Skip List 跳表 | O(log n) 按序 | O(log n) 平均 | O(log n) 平均 |
| 算法 | 平均 / 最坏时间 | 空间 | 稳定性 |
|---|---|---|---|
| Bubble Sort 冒泡 | O(n²) / O(n²)，有序可优化至 O(n) | O(1) | 稳定 |
| Insertion Sort 插入 | O(n²) / O(n²)，基本有序近 O(n) | O(1) | 稳定 |
| Quick Sort 快排 | O(n log n) / O(n²) 有序数据退化 | O(log n) 递归栈 | 不稳定 |
| Merge Sort 归并 | O(n log n) / O(n log n) | O(n) 辅助数组 | 稳定 |
| Heap Sort 堆排 | O(n log n) / O(n log n) | O(1) | 不稳定 |
| Counting / Bucket 计数/桶 | O(n + k)，k 为数据范围 | O(k) | 稳定（桶内排序决定） |
🧠 常用思想
| 思想 / 技巧 | 一句话 | 适用场景 |
|---|---|---|
| 分治 Divide & Conquer | 分解 → 解决 → 合并，要求子问题相互独立、结构相同 | 归并排序、快速排序、最近点对、大整数乘法 |
| 贪心 Greedy | 每步取局部最优，需能证明贪心选择性质 + 最优子结构 | 区间调度、霍夫曼编码、跳跃游戏、分配问题 |
| 二分答案 Binary on Answer | 答案具有单调性时，不直接求解而是二分枚举答案再验证可行性 | 「最小值最大化 / 最大值最小化」、拆分数组、运送天数类问题 |
| 前缀和 Prefix Sum | 预处理累加数组，任意区间和由两端点作差 O(1) 得到 | 静态区间和、子数组和等于 K、二维矩阵区域和 |
| 差分 Difference | 前缀和的逆运算：区间批量增减 O(1) 标记，最后一次前缀和还原 | 多次区间修改、一次最终查询；航班预订、拼车问题 |
| 位运算技巧 Bitmask | 异或消重、n & (n-1) 清最低位 1、二进制枚举子集 | 只出现一次的数、2 的幂判断、状态压缩 DP（n ≤ 20） |
🧩 手写模板易错点
手写模板的坑基本都在边界：mid 取整方向、递归区间搭配、建堆起点——先背对搭配关系再默写，写完用空数组自测。
| 模板 | 易错点 | 规避要点 |
|---|---|---|
| Quick Sort 快排 | 枢轴取端点 + 输入已有序 → 退化 O(n²)；分区指针不动导致死循环 | 随机枢轴或三数取中；partition 用 do-while 保证指针必移动，递归区间为 [l, j] 与 [j+1, r] |
| Merge Sort 归并 | mid 取值与递归区间不配套（mid = (l+r)/2 却递归 [l, mid-1]）漏元素；merge 后忘拷回 | 固定搭配 mid = l + r >> 1、递归 [l, mid] 与 [mid+1, r]；merge 完成后整体回写原数组 |
| Heap 堆 | 建堆从叶子开始白做；下沉时只与左孩子比较漏掉右孩子更大的情况 | 0 起始数组从最后一个非叶子节点 n/2 - 1 倒序下沉；下沉时先选两孩子中较大者再比较 |
| Binary Search 二分 | mid = (l + r) / 2 大数相加溢出；边界 ±1 写错死循环或漏解 | 写 l + (r - l) / 2（Java 可用 (l + r) >>> 1）；先定循环不变量再推 l/r 的更新方式 |
| 二分左边界 | 找第一个 ≥ target 的位置时用 r = mid 却配 mid = (l+r)/2 向下取整 → 死循环 | r = mid 模板必须配向上取整 mid = l + r + 1 >> 1；两套模板不要混用 |
| 通用边界 | 空数组、单元素、全相同元素时越界或返回错误下标 | 先写终止条件再写递归体；自测用例覆盖空 / 单元素 / 全相同 / 有序逆序 必查 |
🧪 复杂度估算实战
动手前先估算：用操作次数量级对照数据范围，判断解法能否通过、还能怎么优化。
| 场景 | 估算要点 | 结论 / 优化方向 |
|---|---|---|
| 双重循环 O(n²) | 外层 n 次里各嵌 n 次比较，约 n²/2 次操作 | n ≤ 1e4 勉强可过，n ≥ 1e5 必超时；固定外层、内层换哈希 O(1) 查找，降到 O(n) |
| T(n) = 2T(n/2) + n | 主定理：a=2、b=2，f(n)=n 与 n^(log₂2) = n 同阶 | 取 O(n log n)——归并排序、建堆、树分治的典型递归形态 |
| 排序后二分 降一维 | 两两配对 O(n²) 中，排序后每个元素可二分找配对 | 消掉一重循环降到 O(n log n)；「有序 + 查找」信号优先想二分 |
| 前缀和预处理 | q 次区间求和，暴力每次 O(n)，总计 O(nq) | 预处理 O(n) + 单次查询 O(1)，总代价 O(n + q)，用预处理换查询 |
| 均摊分析 动态数组 | 扩容翻倍时整体拷贝一次，单次最坏 O(n) | n 次插入总拷贝不超过 2n，均摊每次 O(1)；单次最坏 ≠ 均摊，别被吓退 |
| 数据范围反推 实战技巧 | 1 秒约 1e8 次基本运算，n ≤ 1e5 只容得下 O(n log n) | n ≤ 20 试状压 / 搜索，n ≤ 500 试 O(n³)，n ≥ 1e6 只能 O(n) 或数学解 |
💡 白板答题检查单
面试写题按这六步走一遍，覆盖读题、设计、编码到验证的完整闭环，避免会的题丢分。
| 步骤 | 要做什么 | 易错提醒 |
|---|---|---|
| ① 读题圈约束 | 圈出数据范围 n、值域、有序 / 去重 / 非负等隐藏条件 | 复杂度上限由 n 决定，漏看一个条件就是方向性错误 最常见 |
| ② 先说暴力再优化 | 先给保底的暴力解，再沿着瓶颈讲优化路径 | 闷头沉默硬想最优解，既暴露思路混乱又浪费互动机会 |
| ③ 边界与空输入 | 主动确认空数组、单元素、全相同、极大值四类输入 | 面试官最爱追问「你的代码 n=0 时返回什么」 |
| ④ 整数溢出 | 两数相加 / 乘积可能超 int：升级 long 或边算边取模 | 二分中点写 l + (r - l) / 2；结果要求取模时每一步都取 |
| ⑤ 主动口述复杂度 | 写完立刻说时间 / 空间复杂度，并指出进一步优化空间 | 等面试官追问显得被动；说错复杂度比写得慢更致命 |
| ⑥ 写完走查用例 必做 | 拿一个小用例逐行模拟变量变化，验证每条分支 | off-by-one 与循环终止条件是最高频笔误，走查一遍就能抓住 |