# springDataAlgorithms

**Repository Path**: meiyannan/spring-data-algorithms

## Basic Information

- **Project Name**: springDataAlgorithms
- **Description**: 数据结构与算法
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2026-07-27
- **Last Updated**: 2026-07-27

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# Java 后端业务开发必备数据结构与算法学习项目

> 基于《Java 后端业务开发必备数据结构与算法完整文档》创建，面向普通业务 Java 开发，无竞赛难题、无复杂数学推导。
>
> 🎯 **大白话版**：每个算法都有生活化比喻 + 通俗解释，小白也能看懂。

---

## 目录

- [项目结构总览](#项目结构总览)
- [大白话讲算法](#大白话讲算法)
  - [一、排序算法（6种）](#一排序算法6种)
  - [二、搜索算法（5种）](#二搜索算法5种)
  - [三、分治算法（2种）](#三分治算法2种)
  - [四、贪心算法（1种）](#四贪心算法1种)
  - [五、回溯算法（1种）](#五回溯算法1种)
  - [六、动态规划（1种）](#六动态规划1种)
  - [七、哈希算法（1种）](#七哈希算法1种)
  - [八、设计算法（1种）](#八设计算法1种)
  - [九、预处理算法（1种）](#九预处理算法1种)
  - [十、图论算法（1种）](#十图论算法1种)
- [面试怎么说：真实项目场景](#面试怎么说真实项目场景)
- [算法分类速查表](#算法分类速查表)
- [速度排序（牢记）](#速度排序牢记)
- [一眼判断代码复杂度](#一眼判断代码复杂度)
- [线上优化万能思路](#线上优化万能思路)
- [设计模式学习（GoF 23种）](设计模式README.md)

---

## 项目结构总览

```
src/main/java/org/meiyn/example/
│
├── complexity/                              # 第一部分：时间复杂度 Big-O
│   └── BigODemo.java                        #   5种常用复杂度演示 (O(1) ~ O(n²))
│
├── datastructure/                           # 第二部分：后端八大基础数据结构
│   ├── array/
│   │   └── ArrayDemo.java                   #   数组：下标随机访问 O(1)
│   ├── linkedlist/
│   │   └── LinkedListDemo.java              #   双向链表：头尾增删 O(1)
│   ├── stack/
│   │   └── StackDemo.java                   #   栈：后进先出 LIFO
│   ├── queue/
│   │   └── QueueDemo.java                   #   队列：先进先出 FIFO
│   ├── hashmap/
│   │   └── HashMapOptDemo.java              #   哈希表：O(1) 快速匹配（业务优化核心）
│   ├── treemap/
│   │   └── TreeMapDemo.java                 #   红黑树：自动有序 O(logn)
│   ├── binarytree/
│   │   └── TreeRecursionDemo.java           #   二叉树：递归遍历树形结构
│   └── hashset/
│       └── HashSetDemo.java                 #   哈希集合：批量去重 O(n)
│
├── algorithm/                               # 第三部分：20种核心算法（按分类组织）
│   │
│   ├── sorting/                             #   ===== 排序算法（6种）=====
│   │   ├── QuickSortDemo.java               #   1. 快速排序：递归分治 O(nlogn)
│   │   ├── BubbleSortDemo.java              #   2. 冒泡排序：相邻比较冒泡 O(n²)
│   │   ├── InsertionSortDemo.java           #   3. 插入排序：扑克牌式插入 O(n²)
│   │   ├── HeapSortDemo.java                #   4. 堆排序：大顶堆取顶 O(nlogn)
│   │   ├── BizSortDemo.java                 #   5. 业务复合排序：List.sort() 多维排序
│   │   └── MergeSortedShardDemo.java        #   6. 归并排序：分表有序数据合并
│   │
│   ├── searching/                           #   ===== 搜索算法（5种）=====
│   │   ├── BinarySearchDemo.java            #   7. 二分查找：有序数据 O(logn)
│   │   ├── TwoPointerDemo.java              #   8. 双指针：O(n²) 优化为 O(n)
│   │   ├── SlidingWindowDemo.java           #   9. 滑动窗口：限流、区间统计
│   │   ├── DFSDemo.java                     #  10. DFS深度优先搜索：递归/栈遍历 O(V+E)
│   │   └── BFSDemo.java                     #  11. BFS广度优先搜索：队列层序遍历 O(V+E)
│   │
│   ├── divideconquer/                       #   ===== 分治算法（2种）=====
│   │   ├── RecursionTreeDemo.java           #  12. 递归：树形部门结构组装
│   │   └── DivideHandleDemo.java            #  13. 分治：批量数据分片处理
│   │
│   ├── greedy/                              #   ===== 贪心算法（1种）=====
│   │   └── GreedyCouponDemo.java            #  14. 贪心算法：优惠券最优抵扣
│   │
│   ├── backtrack/                           #   ===== 回溯算法（1种）=====
│   │   └── BacktrackDemo.java               #  15. 回溯算法：组合/排列枚举
│   │
│   ├── dynamicprogramming/                  #   ===== 动态规划（1种）=====
│   │   └── DpPriceDemo.java                 #  16. 动态规划：阶梯价格缓存计算
│   │
│   ├── hash/                                #   ===== 哈希算法（1种）=====
│   │   └── HashDistinctDemo.java            #  17. 哈希去重：HashSet / Stream
│   │
│   ├── design/                              #   ===== 设计算法（1种）=====
│   │   └── LRUCacheDemo.java                #  18. LRU缓存：LinkedHashMap + 手写双向链表
│   │
│   ├── prefixsum/                           #   ===== 预处理算法（1种）=====
│   │   └── PrefixSumDemo.java               #  19. 前缀和：区间和 O(1) 查询 + 差分数组
│   │
│   └── graph/                               #   ===== 图论算法（1种）=====
│       └── TopologicalSortDemo.java         #  20. 拓扑排序：Kahn算法任务依赖排序
│
├── practice/                                # 第四部分：项目通用算法优化实战案例
│   ├── HashMapOptimizeCase.java             #   案例1：List关联查询 HashMap 优化
│   ├── CrossTableQueryCase.java             #   案例2：分表跨月查询 二分+归并
│   ├── RateLimitCase.java                   #   案例3：接口限流 滑动窗口
│   └── TreeMenuCase.java                    #   案例4：树形菜单 递归组装
│
└── designpattern/                           # 第五部分：GoF 23种设计模式（按分类组织）
    │
    ├── creational/                          #   ===== 创建型模式（5种）=====
    │   ├── singleton/
    │   │   └── SingletonDemo.java           #   1. 单例模式：饿汉/懒汉/枚举
    │   ├── factorymethod/
    │   │   └── PayFactoryDemo.java          #   2. 工厂方法：支付渠道工厂
    │   ├── abstractfactory/
    │   │   └── DatabaseFactoryDemo.java     #   3. 抽象工厂：多数据库适配
    │   ├── builder/
    │   │   └── OrderBuilderDemo.java        #   4. 建造者：链式构建复杂订单
    │   └── prototype/
    │       └── PrototypeDemo.java           #   5. 原型模式：深浅拷贝
    │
    ├── structural/                          #   ===== 结构型模式（7种）=====
    │   ├── adapter/
    │   │   └── LogAdapterDemo.java          #   6. 适配器：日志框架适配
    │   ├── decorator/
    │   │   └── BeverageDecoratorDemo.java   #   7. 装饰器：奶茶加料
    │   ├── proxy/
    │   │   └── AopProxyDemo.java            #   8. 代理：JDK动态代理+CGLIB
    │   ├── facade/
    │   │   └── OrderFacadeDemo.java         #   9. 外观：下单流程聚合
    │   ├── bridge/
    │   │   └── MessageBridgeDemo.java       #  10. 桥接：消息类型×发送渠道
    │   ├── composite/
    │   │   └── MenuTreeDemo.java            #  11. 组合：菜单树统一处理
    │   └── flyweight/
    │       └── IntegerCacheDemo.java        #  12. 享元：Integer缓存机制
    │
    └── behavioral/                          #   ===== 行为型模式（11种）=====
        ├── strategy/
        │   └── PayStrategyDemo.java         #  13. 策略：支付方式+Spring注入
        ├── template/
        │   └── ExportTemplateDemo.java      #  14. 模板方法：数据导出骨架
        ├── observer/
        │   └── OrderEventDemo.java          #  15. 观察者：Spring事件机制
        ├── iterator/
        │   └── CustomIteratorDemo.java      #  16. 迭代器：自定义集合遍历
        ├── chain/
        │   └── RiskControlChainDemo.java    #  17. 责任链：风控审核链
        ├── command/
        │   └── OrderCommandDemo.java        #  18. 命令：订单操作撤销重做
        ├── memento/
        │   └── ConfigMementoDemo.java       #  19. 备忘录：配置回滚
        ├── state/
        │   └── OrderStateMachineDemo.java   #  20. 状态：订单状态机
        ├── visitor/
        │   └── ReportVisitorDemo.java       #  21. 访问者：报表多视角
        ├── mediator/
        │   └── ChatRoomMediatorDemo.java    #  22. 中介者：聊天室
        └── interpreter/
            └── RuleEngineDemo.java          #  23. 解释器：简单规则引擎
```

---

## 大白话讲算法

> 每个算法用 **生活化比喻** 解释，看完就能理解核心思想。

### 一、排序算法（6种）

#### 1. 快速排序（QuickSortDemo.java）

**大白话**：想象一群人站成一排按身高排序。你随便挑一个人当"标杆"，比他矮的站左边，比他高的站右边。然后左右两拨人各自再挑标杆继续分……一直分到每拨只剩一个人，大家就自然站好了。

**生活中的例子**：体育课排队，老师挑一个同学站中间，矮的左边高的右边，然后左右两边再各挑一个中间人继续分。

**核心步骤**：
1. 选一个数当"基准"（通常选第一个）
2. 比 basis 小的放左边，大的放右边
3. 左右两边各自重复第 1~2 步
4. 分到每边只剩一个数时，排序完成

**时间复杂度**：平均 O(nlogn)，最坏 O(n²)（运气差每次选到最大/最小当基准）

---

#### 2. 冒泡排序（BubbleSortDemo.java）

**大白话**：就像水里的气泡，越大的气泡浮得越快。每一轮从头到尾两两比较，大的往后换，一轮下来最大的就"冒泡"到最后了。优化版：如果某一轮一次交换都没有，说明已经排好了，直接收工。

**生活中的例子**：排队时，相邻两个人比身高，高的往后站，一轮下来最高的人就排到最后了。

**核心步骤**：
1. 第 1 轮：从第 1 个比到最后一个，每次相邻两个比，大的往后换 → 最大的到了最后
2. 第 2 轮：从第 1 个比到倒数第二个 → 第二大的到了倒数第二
3. 重复 n-1 轮，排序完成
4. 优化：某一轮没发生交换 → 已经排好了，提前结束

**时间复杂度**：O(n²) 平均/最坏，O(n) 最好（已有序 + 优化版）

---

#### 3. 插入排序（InsertionSortDemo.java）

**大白话**：就是打扑克牌时整理手牌的方式。你手里已经有几张排好的牌，新摸一张，从右往左找到合适的位置插进去。手里的牌始终是有序的。

**生活中的例子**：斗地主时，你摸到一张牌，从右往左看，找到比它小的牌，插在它后面。

**核心步骤**：
1. 把第 1 个数当成"已排好的"
2. 拿第 2 个数，跟左边的数从右往左比，比它大的往右挪一格，找到位置插进去
3. 拿第 3 个数，同样操作
4. 重复到最后一个数

**时间复杂度**：O(n²) 平均/最坏，O(n) 最好（已经排好了，每次只比较一次就插入）

---

#### 4. 堆排序（HeapSortDemo.java）

**大白话**：想象一个公司的组织架构，能力最强的人在最顶上（大顶堆）。每次把最强的（堆顶）拿走放到最后，剩下的人重新选出最强的当堆顶，再拿走……拿完就排好了。

**生活中的例子**：选秀节目，每次选出最强的选手（冠军）放到荣誉墙第一位，然后剩下的人再选最强的放第二位……最后荣誉墙上就是按实力排序的。

**核心步骤**：
1. 把数组调整成"大顶堆"（每个节点都比子节点大）
2. 堆顶（最大值）和最后一个元素交换 → 最大值到了末尾
3. 缩小堆的范围（末尾那个不算了），重新调整堆顶
4. 重复步骤 2~3，直到堆只剩一个元素

**时间复杂度**：O(nlogn)（不管什么情况都一样，这是堆排序的优势）

---

#### 5. 业务复合排序（BizSortDemo.java）

**大白话**：日常开发中不需要手写排序算法，Java 自带的 `List.sort()` 就够用了。你只需要写个 Comparator 告诉它"先按什么排，再按什么排"。比如：先按状态降序（待处理的排前面），状态一样就按金额降序（钱多的排前面）。

**生活中的例子**：超市收银排队，VIP 客户优先，同为 VIP 的按到达时间排，都不是 VIP 的按到达时间排。

**核心步骤**：
1. 定义排序规则（Comparator）
2. 调用 `List.sort(comparator)`
3. Java 底层自动用 TimSort（归并+插入的混合版）帮你排好

**时间复杂度**：O(nlogn)（Java 底层 TimSort 保证）

---

#### 6. 归并/双指针排序（MergeSortedShardDemo.java）

**大白话**：两个已经排好序的队列要合成一个，怎么做？两个队列各站一个人，比一比谁小，小的先出队，最后合并完自然就是有序的。这在分库分表场景特别有用——每个分表的数据是有序的，合并起来就是全局有序。

**生活中的例子**：两个班的学生按身高排好队了，现在要合成一队还是按身高排。两个班排头的人比一下，矮的先站过来，一直比下去就合好了。

**核心步骤**：
1. 两个指针分别指向两个有序列表的开头
2. 比较两个指针指向的元素，小的放进结果列表，该指针后移
3. 某个列表先走完了，把另一个列表剩下的全追加进去
4. 如果是多个列表，两两合并直到合成一个

**时间复杂度**：O(nlogn)

---

### 二、搜索算法（5种）

#### 7. 二分查找（BinarySearchDemo.java）

**大白话**：猜数字游戏！1 到 100 之间猜一个数，你每次猜中间的数，对方告诉你"大了"还是"小了"，你就能每次排除一半。最多猜 7 次就能找到（因为 2⁷ = 128 > 100）。

**生活中的例子**：字典查单词，你不会从第一页翻到最后一页，而是翻到中间，看当前字母比目标大还是小，然后在另一半继续翻中间。

**核心步骤**：
1. 前提：数据必须是有序的
2. 取中间位置的值，跟目标比
3. 中间值 == 目标 → 找到了
4. 中间值 < 目标 → 目标在右半边，左边界移到 mid+1
5. 中间值 > 目标 → 目标在左半边，右边界移到 mid-1
6. 重复直到找到或左边界超过右边界（没找到）

**时间复杂度**：O(logn) —— 1024 条数据最多查 10 次（2¹⁰ = 1024）

---

#### 8. 双指针（TwoPointerDemo.java）

**大白话**：两个人从队伍两头往中间走。左边的问"我加你等于目标吗？"，小于目标左边往前走一步，大于目标右边往回走一步，直到找到答案或两人碰面。

**生活中的例子**：在一排按身高站好的学生里，找两个人身高加起来等于 3 米。最矮的和最高的先加，不够就让矮的换高一点，超了就让高的换矮一点。

**核心步骤**：
1. 前提：数据有序
2. 左指针在开头，右指针在末尾
3. 两数之和 == 目标 → 找到了
4. 之和 < 目标 → 左指针右移（让和变大）
5. 之和 > 目标 → 右指针左移（让和变小）
6. 重复直到找到或两指针相遇

**时间复杂度**：O(n) —— 两个人合起来最多走 n 步

---

#### 9. 滑动窗口（SlidingWindowDemo.java）

**大白话**：想象一个固定大小的"窗口"在数据上从左往右滑动。窗口每往右移一格，只需要加上新进来的那个数、减去旧出去的那个数，不用把窗口里的数重新加一遍。这样统计就快多了。

**生活中的例子**：你每天记录体重，想知道"最近 7 天平均体重"。不需要每天把 7 天的体重全加一遍，只需要：昨天的 7 天平均 × 7 - 7 天前的体重 + 今天的体重，再除以 7。

**核心步骤**：
1. 先算第一个窗口的值（比如前 k 个元素的和）
2. 窗口右移一格：减去左边出去的元素，加上右边进来的元素
3. 比较当前窗口值和最大值，更新最大值
4. 重复直到窗口滑到末尾

**时间复杂度**：O(n) —— 窗口只扫一遍数据

---

#### 10. DFS 深度优先搜索（DFSDemo.java）

**大白话**：走迷宫的方式——一条路走到黑，走不通了退回来换条路继续走。先往深处探索，碰壁了就回退。

**生活中的例子**：你在商场找一家店，顺着一条走廊走到头没找到，退回岔路口换另一条走廊继续走，直到找到为止。

**核心步骤**：
1. 从起点出发，标记为"已访问"
2. 随便挑一个没走过的邻居，继续深入
3. 走到没路了（所有邻居都走过了），退回上一个节点
4. 从上一个节点挑另一条没走过的路继续
5. 重复直到所有节点都访问过

**时间复杂度**：O(V+E)（V 是节点数，E 是边数）

---

#### 11. BFS 广度优先搜索（BFSDemo.java）

**大白话**：像水波纹一样一圈一圈往外扩散。先访问离起点最近的，再访问远一层的，一层一层扩展。好处是找到目标时一定是"最短路径"。

**生活中的例子**：你在朋友圈找人，先问你的直接好友（第 1 层），好友不认识就问好友的好友（第 2 层），一层层扩散下去，找到的第一个人一定是你关系最近的那条链路。

**核心步骤**：
1. 起点入队，标记为"已访问"
2. 从队列取出一个节点，处理它
3. 把它的所有未访问邻居加入队列
4. 重复步骤 2~3，直到队列为空
5. 找目标时，第一次碰到就是最短路径

**时间复杂度**：O(V+E)

---

### 三、分治算法（2种）

#### 12. 递归（RecursionTreeDemo.java）

**大白话**：俄罗斯套娃！大的套娃里面套着小的，小的里面还套着更小的。打开的过程就是递归——每次做同样的事情，只是规模变小了，直到最小的那个（终止条件）。

**生活中的例子**：查家谱，你想知道某个人下面有多少后代。你先看他的直接下属（孩子），对每个孩子再看他们的孩子……一层层往下查，直到没有孩子的人为止。

**核心步骤**：
1. 明确"大问题"和"小问题"的关系（大问题 = 小问题 + 处理逻辑）
2. 设定终止条件（什么时候不再递归）
3. 调用自己处理小问题
4. 合并小问题的结果

**时间复杂度**：看具体问题，从 O(n) 到 O(2ⁿ) 都有可能

---

#### 13. 分治（DivideHandleDemo.java）

**大白话**：一大堆活一个人干不完？拆成几小堆分给不同的人干，每个人干完了汇报结果，最后汇总。核心思想就是"分而治之"。

**生活中的例子**：公司要处理 10 万条订单数据，一条条处理太慢。拆成 10 批每批 1 万条，10 个线程同时处理，最后合并结果。

**核心步骤**：
1. 分：把大问题拆成相同结构的小问题
2. 治：递归求解每个小问题
3. 合：把小问题的结果合并成大问题的解

**时间复杂度**：O(nlogn)（拆 logn 层，每层处理 n 个）

---

### 四、贪心算法（1种）

#### 14. 贪心算法（GreedyCouponDemo.java）

**大白话**：买东西时，手上有几张优惠券，每次都挑抵扣最多的那张先用。不考虑"用这张会不会导致后面更划算"，只管眼前最优。

**生活中的例子**：双十一凑单满减，你手上有多张优惠券。贪心策略就是：按抵扣金额从大到小排，能用的先用，不纠结组合最优。

**核心步骤**：
1. 把所有选项按某个标准排序（比如抵扣金额降序）
2. 从前往后遍历，满足条件就用
3. 不回头、不后悔，选了就选了

**时间复杂度**：O(nlogn)（排序主导）

---

### 五、回溯算法（1种）

#### 15. 回溯算法（BacktrackDemo.java）

**大白话**：走迷宫的高级版——不仅走不通要退回来，还要把每条可能的岔路都试一遍，记录所有能走通的路线。核心是"试探 + 撤销"。

**生活中的例子**：密码锁有 3 位数字，你不知道密码，就从 000 试到 999。每试一个不对就换下一个，这就是回溯的思想。

**核心步骤**：
1. 做选择：选一个可能的选项
2. 递归：基于这个选择继续往下探索
3. 撤销选择：这条路的探索完了，撤销刚才的选择，换下一个选项
4. 重复直到所有可能性都试过

**时间复杂度**：O(2ⁿ)（组合问题）或 O(n!)（排列问题）

---

### 六、动态规划（1种）

#### 16. 动态规划（DpPriceDemo.java）

**大白话**：好记性不如烂笔头。有些问题会反复计算相同的子问题，与其每次重新算，不如第一次算完后把结果记在表里，下次直接查表。

**生活中的例子**：你计算 1+2+3+...+100，如果已经算过 1+2+...+50 = 1275，那 1+2+...+100 = 1275 + 51 + 52 + ... + 100，不用从头加。

**核心步骤**：
1. 定义状态：dp[i] 代表什么含义（比如 dp[i] = 买 i 件商品的总价）
2. 找状态转移方程：dp[i] 和 dp[i-1] 的关系
3. 确定初始值：dp[0] = 0, dp[1] = ?
4. 从小到大填表，最后 dp[n] 就是答案

**时间复杂度**：O(n)（预处理一次，之后每次查询 O(1)）

---

### 七、哈希算法（1种）

#### 17. 哈希去重（HashDistinctDemo.java）

**大白话**：HashSet 就像一个"不允许重复"的袋子，你把数据一个一个往里扔，重复的自动被拒绝，最后袋子里就是去重后的结果。

**生活中的例子**：你有一堆名片想去重，按名字排序再挑太麻烦。直接拿个带"名字锁"的盒子，每张名片试着放进去，名字一样的放不进去，最后盒子里就是去重后的。

**核心步骤**：
1. 创建一个 HashSet
2. 把所有数据 add 进去（重复的自动被忽略）
3. HashSet 里的数据就是去重后的结果

**时间复杂度**：O(n)（每个元素 add 是 O(1)）

---

### 八、设计算法（1种）

#### 18. LRU 缓存（LRUCacheDemo.java）

**大白话**：缓存就像你的书桌，空间有限放不下所有书。放满了就把最久没翻过的那本收起来，给新书腾位置。这就是 LRU（Least Recently Used，最近最少使用）。

**生活中的例子**：手机后台 App 管理，内存不够了就先杀掉最久没打开的 App。你刚用过的 App 不会被杀，一直不用的先被清理。

**核心步骤**：
1. 访问/写入一个数据时，把它移到"最近使用"的头部
2. 新数据进来且缓存满了时，淘汰"最久没用"的尾部数据
3. 底层用 HashMap + 双向链表实现：HashMap 保证 O(1) 查找，双向链表保证 O(1) 移动节点

**时间复杂度**：get / put 都是 O(1)

---

### 九、预处理算法（1种）

#### 19. 前缀和（PrefixSumDemo.java）

**大白话**：提前把"从头到每个位置的累加和"算好存起来。之后问你"第 3 个到第 7 个的和是多少"，不用从头加到尾，直接用 `前缀和[7] - 前缀和[2]` 就出来了。

**生活中的例子**：你每天记账存余额，到月底想知道 15 号到 20 号花了多少钱，不用把 15~20 号的消费一笔笔加，直接用"20 号余额 - 14 号余额"就行。

**核心步骤**：
1. 构建前缀和数组：prefixSum[i] = arr[0] + arr[1] + ... + arr[i-1]
2. 查询区间 [left, right] 的和：prefixSum[right+1] - prefixSum[left]
3. 差分数组（逆操作）：支持区间批量加值，最后还原

**时间复杂度**：预处理 O(n)，每次查询 O(1)

---

### 十、图论算法（1种）

#### 20. 拓扑排序（TopologicalSortDemo.java）

**大白话**：安排任务执行顺序，有依赖关系的必须先做前置任务。比如"穿鞋"必须先"穿袜"，"穿袜"必须先"穿裤"。拓扑排序就是帮你排出一个合理的执行顺序。

**生活中的例子**：大学排课，"数据结构"需要先修"C 语言"，"算法"需要先修"数据结构"。拓扑排序帮你排出：C 语言 → 数据结构 → 算法。

**核心步骤**：
1. 统计每个节点的"入度"（有多少个前置依赖）
2. 入度为 0 的节点入队（没有前置依赖，可以直接做）
3. 取出队首节点，把它指向的后继节点入度 -1
4. 后继节点入度变成 0 了就入队
5. 重复直到队列为空。如果还有节点没处理 → 存在循环依赖

**时间复杂度**：O(V+E)

---

## 面试怎么说：真实项目场景

> 面试官问"你在项目中用过哪些算法？"或"讲一个你做过的性能优化"时，以下是每种算法的**真实回答素材**，覆盖电商、金融、物流等业务场景，涉及 Spring Boot、Redis、MySQL、MQ 等技术栈。

### 一、排序算法

#### 1. 快速排序

**面试一句话**：电商首页热销榜单从 Redis 拉到内存后用快速排序实时重排，避免每次都查数据库 ORDER BY。

**真实场景**：
- **电商商品榜单**：Spring Boot 项目中，首页"实时热销 TOP50"从 Redis ZSET 拉取数据后，需要按"最近 1 小时销量 × 商品权重"复合规则重新排序。数据库 ORDER BY 走不了合适索引，改成从 Redis 拉 List 到内存用快排，响应时间从 800ms 降到 50ms
- **直播打赏榜**：直播间礼物贡献榜，主播开播期间观众打赏数据高频变更，每 3 秒从 Redis 拉全量打赏数据到内存快排后推前端 WebSocket
- **Java 底层**：`Arrays.sort()` 对基本类型用双轴快速排序（Dual-Pivot QuickSort），面试可以提这个知识点

---

#### 2. 冒泡排序

**面试一句话**：支付网关轮询可用支付渠道时，渠道列表不到 10 个且基本有序，用冒泡比快排更高效。

**真实场景**：
- **支付渠道路由**：Spring Boot 支付系统，维护 6~8 个支付渠道（微信、支付宝、银联等），按"成功率优先 + 响应时间次之"排序后轮询。渠道列表几乎不变、每次只微调顺序，冒泡排序的"近乎有序"场景时间复杂度接近 O(n)，比快排的递归开销更小
- **面试加分**：说出"小数据量（<47）或近乎有序时，Java 的 `Arrays.sort()` 也会切换为插入排序，思路类似" -- 展示你对 JDK 底层的了解

---

#### 3. 插入排序

**面试一句话**：金融交易流水中新来一条交易，插入到已排序序列中保持有序，用插入排序的"在线"特性。

**真实场景**：
- **交易流水在线排序**：Spring Boot 金融系统，交易流水按时间戳保持有序。新交易到来时用插入排序思路，从尾部往前比较找到位置插入，只需移动少量元素，时间复杂度接近 O(n)。比每次全量重排高效
- **JDK 底层**：`Arrays.sort()` 对长度 < 47 的数组自动切换插入排序；`Collections.sort()` 底层 TimSort 在小数组时也用插入排序。面试提这个体现底层功底
- **Spring Batch 增量处理**：批量 ETL 任务中，新增数据插入已排序的数据集，用插入排序保持有序

---

#### 4. 堆排序

**面试一句话**：电商热搜榜实时维护 Top-10，用 PriorityQueue 小顶堆，新数据比堆顶大就替换，不用每次全量排序。

**真实场景**：
- **热搜榜 Top-K**：Spring Boot 电商系统，实时维护"最近 1 小时搜索量 Top-10 热搜词"。用 `PriorityQueue`（小顶堆，容量 10），每个搜索关键词的计数更新后与堆顶比较：比堆顶大就入堆，小的就丢弃。避免了每次对全量搜索词（百万级）排序，时间复杂度 O(nlogK) 远优于 O(nlogn) 全量排序
- **Java 线程池调度**：`ScheduledThreadPoolExecutor` 内部用 `DelayedWorkQueue`（堆结构）管理定时任务，每次取最近到期的任务执行。面试可以提"线程池的延迟队列底层就是堆"
- **金融风控 Top-K**：实时计算金额最大的 K 笔异常交易，用堆维护避免全量排序
- **大文件 Top-K**：日志文件中找出访问量 Top-10 的 IP，内存放不下全量数据，分批读取 + 堆维护

---

#### 5. 业务复合排序

**面试一句话**：Spring Boot 订单管理后台多维度排序，先按状态优先级再按金额降序，用 List.sort() + Comparator 一行搞定，减轻数据库 filesort 压力。

**真实场景**：
- **电商订单列表**：Spring Boot + MyBatis 查出订单数据后内存排序，规则是"待付款 > 待发货 > 已发货 > 已完成 > 已取消"（状态优先级），同状态按金额降序，同金额按下单时间降序。原本 SQL 的 `ORDER BY` 导致 MySQL filesort 严重慢查询，改成查出后在 Java 内存排序，SQL 只走索引查数据不排序，QPS 提升 3 倍
- **金融账单排序**：信用卡账单列表，"逾期 > 未还 > 已还" + "金额降序" + "到期日升序"
- **客服工单排序**：优先级（紧急 > 高 > 中 > 低）+ 创建时间（越早越优先），Spring Boot 项目中 `List.sort(Comparator.comparing(...).thenComparing(...).reversed())` 链式调用

---

#### 6. 归并排序

**面试一句话**：分库分表按月分表查询账单，12 张子表各自有序，用归并排序合并成全局有序结果。

**真实场景**：
- **分库分表跨表查询**：Spring Boot + ShardingSphere 金融系统，账单表按月分表（bill_202401, bill_202402...），跨月查询时各分表数据按 bill_id 有序，用归并排序（多路归并）合并 12 个有序 List，时间复杂度 O(nlogk)（k 是分表数），比合并后全量排序 O(nlogn) 更快
- **多数据源合并**：ES 搜索结果 + MySQL 补充数据，两个有序列表归并合并
- **大批量报表导出**：Spring Boot 导出 10 万条数据到 Excel，分 10 批查库每批 1 万条（各自有序），归并合并后写入文件，避免内存溢出

---

### 二、搜索算法

#### 7. 二分查找

**面试一句话**：按月分表路由时用二分查找定位目标月份表，12 张表 O(1) 定位而不是遍历。

**真实场景**：
- **分表路由**：Spring Boot + MyBatis 订单系统，订单表按月分 12 张表。根据查询时间范围用二分查找定位目标子表，避免遍历所有分表。12 张表最多比较 4 次（log₂12 ≈ 3.6）
- **Redis 底层**：Redis ZSET 底层跳表 + 二分查找定位元素位置，面试提这个展示对 Redis 内部结构的理解
- **日志检索**：ELK 系统中，按时间戳二分定位日志文件中的某个时间段，比从头扫描快几个数量级
- **金融流水号检索**：银行流水号是有序递增的，用二分查找快速定位某笔交易，O(logn) 比 O(n) 全量扫描快百倍

---

#### 8. 双指针

**面试一句话**：Spring Boot 对账系统两个有序流水列表逐条比对找差异，双指针一次遍历完成，O(n) 替代 O(n²) 双重循环。

**真实场景**：
- **银企对账**：Spring Boot 金融系统，每天将系统内部交易流水与银行回单流水比对。两边流水按交易时间有序，用双指针逐条比对：时间相同的比对金额，不匹配的标记差异。双指针 O(n+m) 替代嵌套循环 O(n×m)，10 万条对账从 30 分钟降到 2 秒
- **价格区间过滤**：电商商品价格按升序排列，用户筛选 100~500 元商品，双指针定位左右边界一次扫描完成
- **ES 分片结果合并**：ElasticSearch 多分片查询返回多个有序列表，双指针归并成一个有序结果

---

#### 9. 滑动窗口

**面试一句话**：Spring Cloud Gateway 用滑动窗口实现接口限流，Redis 维护时间戳队列，窗口滑动时只增减边界数据，O(1) 判断是否放行。

**真实场景**：
- **接口限流**：Spring Cloud Gateway + Redis 实现滑动窗口限流。每次请求将当前时间戳存入 Redis LinkedList，移除窗口外过期请求，判断窗口内请求数是否超阈值。比固定窗口更平滑，解决了窗口边界的"突发流量"问题。Sentinel 也用滑动窗口统计 QPS
- **秒杀监控**：电商秒杀活动，滑动窗口实时统计最近 1 秒 QPS，超过阈值触发降级熔断
- **金融风控**：统计用户最近 5 分钟内交易次数，滑动窗口实时更新，超阈值触发风控告警
- **直播弹幕**：滑动窗口统计最近 10 秒弹幕量，控制弹幕显示频率

---

#### 10. DFS 深度优先搜索

**面试一句话**：Spring Boot 权限系统递归遍历菜单树组装前端路由，DFS 从根菜单出发深度遍历子菜单到叶子节点。

**真实场景**：
- **菜单/权限树组装**：Spring Boot + MyBatis 后台管理系统，用户登录后根据角色查出拥有的菜单权限（扁平 List），用 DFS 递归组装成前端需要的树形 JSON。这是后端最常见的递归场景，几乎每个后台系统都有
- **商品分类无限层级**：电商系统商品分类支持无限层级嵌套（数码 > 手机 > 苹果 > iPhone 15），DFS 递归组装分类树返回前端级联选择器
- **微服务链路追踪**：SkyWalking/Pinpoint 用 DFS 遍历分布式调用树，展示完整的微服务调用链路
- **文件目录扫描**：Spring Boot 文件管理模块，递归扫描目录下所有文件（DFS 天然适配树形结构）

---

#### 11. BFS 广度优先搜索

**面试一句话**：社交电商"找人"功能用 BFS 找最短关系链，从用户出发逐层扩展好友圈，找到目标时关系链最短。

**真实场景**：
- **社交好友推荐**：Spring Boot + Neo4j 社交电商，"你可能认识的人"功能。从当前用户出发 BFS 遍历好友关系图，第 2 层就是"二度人脉"推荐，第 3 层是"三度人脉"。BFS 保证找到的是最短关系链
- **组织架构层级展示**：企业 OA 系统，BFS 层序遍历部门树，前端按层级展示组织架构图
- **消息广播**：Spring Boot + WebSocket 消息推送系统，从根节点 BFS 逐层推送给下级节点
- **最短路径**：物流配送系统，城市间有中转路线图，BFS 找从仓库到目的地的最短中转路径

---

### 三、分治算法

#### 12. 递归

**面试一句话**：Spring Boot 后台管理系统几乎每个都有菜单树/部门树/权限树，递归组装是后端必备技能。

**真实场景**：
- **菜单树组装**：Spring Boot + MyBatis 后台系统，数据库存扁平菜单记录（id, name, parent_id），查出全部菜单 List 后递归组装：找 parentId=0 的根菜单，对每个根菜单递归找子菜单，子菜单再找子菜单……最终组装成前端需要的树形 JSON
- **部门树**：企业 OA 系统组织架构，递归组装多级部门树
- **SKU 规格笛卡尔积**：电商商品多规格组合（颜色 × 尺寸 × 材质），递归生成所有 SKU 组合。比如 3 颜色 × 4 尺寸 × 2 材质 = 24 个 SKU
- **JSON 嵌套解析**：递归解析多层嵌套的 JSON 配置结构

---

#### 13. 分治

**面试一句话**：Spring Batch 处理 100 万条订单数据，分 100 批每批 1 万条线程池并发处理，分治思想防 OOM。

**真实场景**：
- **大数据量分批处理**：Spring Boot + 线程池处理 100 万条订单数据同步。一次性加载到内存会 OOM，用分治思想拆成 100 批每批 1 万条，线程池 10 个线程并发处理，每批处理完释放内存。最后汇总统计结果
- **分库分表聚合统计**：ShardingSphere 分库分表后，各分表并行执行 COUNT/SUM，最后合并结果。比单库全表扫描快几倍
- **ES 分片查询**：ElasticSearch 查询分散到多个分片并行执行，各分片结果归并合并返回

---

### 四、贪心算法

#### 14. 贪心算法

**面试一句话**：电商结算页多张优惠券最优抵扣，按抵扣金额降序贪心选择，满足门槛就用，简单高效。

**真实场景**：
- **优惠券最优抵扣**：Spring Boot 电商结算页，用户有多张优惠券（满 100 减 30、满 200 减 60、满 500 减 150），订单金额 600 元。贪心策略：按抵扣金额降序排，满 500 减 150 先用（抵扣最多），剩余 450 再看满 200 减 60，最后满 100 减 30，总抵扣 240 元。虽然不一定是全局最优组合，但实现简单且大部分场景够用
- **满减凑单推荐**：电商"满 299 减 50"活动，贪心推荐价格最接近差额的商品凑单
- **物流仓库选择**：多仓发货，贪心选距离收货地址最近的仓库，减少物流成本
- **广告位分配**：信息流广告按 CPM（千次展示收益）降序贪心分配广告位

---

### 五、回溯算法

#### 15. 回溯算法

**面试一句话**：电商促销方案组合枚举，满减+折扣+优惠券的合法组合方案用回溯穷举所有可能选最优。

**真实场景**：
- **促销组合方案**：Spring Boot 电商营销系统，一个订单可以同时使用"满减活动 + 优惠券 + 会员折扣"，但有限制规则（某些活动互斥、某些有数量上限）。用回溯算法枚举所有合法组合，计算每种组合的最终价格，选最优方案
- **权限组合枚举**：RBAC 权限系统，某个角色需要分配权限组合，给定资源约束条件，回溯枚举满足条件的权限分配方案
- **排课系统**：大学排课，课程有时间槽和教室约束，回溯枚举所有可能的排课方案
- **金融风控规则组合**：风控引擎多规则组合判断，回溯枚举所有触发的规则组合

---

### 六、动态规划

#### 16. 动态规划

**面试一句话**：电商阶梯定价（批发越多越便宜），预计算 dp 数组把每次询价从 O(n) 变成 O(1) 查表。

**真实场景**：
- **阶梯价格计算**：Spring Boot 电商 B2B 批发系统，采购 1~100 件单价 5 元，101~500 件单价 3 元，500+ 件单价 1 元。用 DP 预计算 `dp[i]` = 买 i 件的总价，`dp[i] = dp[i-1] + 当前阶梯单价`。预计算一次后每次询价 O(1) 查表，不用每次从头算
- **金融阶梯费率**：代扣手续费按月交易量阶梯计算（1 万以下 0.1%，1~10 万 0.05%，10 万以上 0.01%），DP 预计算
- **积分阶梯兑换**：积分商城不同积分区间兑换比例不同，DP 预计算最优兑换方案
- **报表累计统计**：Spring Boot 报表系统，月累计/季累计/年累计金额，DP 思路预计算前缀和

---

### 七、哈希算法

#### 17. 哈希去重

**面试一句话**：Spring Boot 批量导入 Excel 手机号用 HashSet 一行去重，MQ 消费用 HashSet 保证幂等性。

**真实场景**：
- **Excel 批量导入去重**：Spring Boot + EasyExcel 批量导入 1 万条客户手机号，同一批数据可能有重复。用 `new HashSet<>(phoneList)` 一行去重，O(n) 完成
- **MQ 消费幂等**：Spring Boot + RocketMQ 消费订单消息，用 HashSet 维护已处理的订单号，防止消息重复消费导致重复发货。生产环境通常用 Redis SET 替代内存 HashSet
- **UV 统计**：Redis `PFADD`（HyperLogLog）或 `SADD`（Set）统计页面 UV，自动去重
- **标签去重**：用户画像系统，用户多个标签来源合并时用 HashSet 去重

---

### 八、设计算法

#### 18. LRU 缓存

**面试一句话**：Spring Boot + Caffeine 本地缓存用 LRU 淘汰策略，Redis 配 allkeys-lru 内存满了自动淘汰最久没用的 key。

**真实场景**：
- **Caffeine/Guava 本地缓存**：Spring Boot 电商系统，商品详情页用 Caffeine 做本地缓存（最大 1000 个商品），LRU 淘汰最久没访问的商品。热点商品常驻缓存，冷门商品自动淘汰，缓存命中率 85%+
- **Redis 内存淘汰**：Redis 配 `maxmemory-policy allkeys-lru`，内存满了自动淘汰最久没用的 key。面试必问 Redis 淘汰策略（LRU/LFU/random/TTL）
- **MyBatis 二级缓存**：MyBatis 二级缓存默认 LRU 策略（`<cache eviction="LRU"/>`），缓存 SQL 查询结果，最久没执行的 SQL 结果被淘汰
- **Spring Cache**：`@Cacheable` 注解底层用 ConcurrentHashMap 或 Redis，配合 LRU 控制缓存大小
- **ThreadLocal 内存泄漏**：面试可以提"ThreadLocal 的 Entry 继承 WeakReference，但如果不 remove 仍可能内存泄漏，跟 LRU 淘汰是两类问题"

---

### 九、预处理算法

#### 19. 前缀和

**面试一句话**：Spring Boot 报表系统用前缀和预计算，区间金额统计从 O(n) 遍历变成 O(1) 减法查询。

**真实场景**：
- **报表区间统计**：Spring Boot + MyBatis 报表系统，每日销售额存数组 `[120, 150, 200, 180, 90...]`，前端要查"第 3 天到第 15 天总销售额"。用前缀和预计算 `prefixSum[15] - prefixSum[2]`，O(1) 查询替代 O(n) 遍历加和
- **用户行为区间统计**：统计用户某段时间内活跃天数，前缀和 O(1) 查询
- **股票涨跌区间**：金融系统计算某时间段内股票涨跌幅，前缀和预处理后区间求和 O(1)
- **差分数组批量更新**：运营给某区间内所有商品价格加 10 元，差分数组只改两个端点 O(1)，最后还原 O(n)。比逐个更新 O(k) 高效

---

### 十、图论算法

#### 20. 拓扑排序

**面试一句话**：Spring Bean 初始化按依赖关系拓扑排序，CI/CD 编译模块也用拓扑排序确定编译顺序。

**真实场景**：
- **Spring Bean 初始化**：Spring 容器启动时，Bean 之间有依赖关系（A 依赖 B，B 依赖 C），Spring 用拓扑排序确定初始化顺序：先创建 C，再创建 B，再创建 A。如果有循环依赖（A 依赖 B，B 依赖 A），Spring 会报错（非构造器注入通过三级缓存解决）
- **CI/CD 编译排序**：Jenkins/GitLab CI 多模块项目编译，模块间有依赖（common 模块先编译，再编译依赖 common 的业务模块），用拓扑排序确定编译顺序
- **电商课程排课**：在线教育平台，课程有先修关系（学"Spring Boot"前先学"Java 基础"），拓扑排序排出合理的学习路径
- **金融清算流程**：银行日终清算，各步骤有依赖关系（先对账再清算再出报表），拓扑排序确定执行顺序，检测循环依赖避免死锁
- **数据仓库 ETL**：Spark/Flink ETL 任务有依赖关系，Airflow/DolphinScheduler 用拓扑排序调度任务

---

### 面试回答模板

> 面试官问"讲一个你在项目中用算法解决的性能问题"，可以套这个模板：

```
场景：我们在 [Spring Boot 电商/金融] 项目中遇到 [具体业务问题]。
问题：原来用 [暴力方案]，数据量到 [N 万/百万] 时 [慢/超时/内存溢出]。
方案：我用 [算法名] 优化，核心思路是 [一句话大白话]。
效果：时间复杂度从 O(?) 降到 O(?)，实际响应时间从 [X] 降到 [Y]。
```

**示例**：
> 场景：Spring Boot 电商订单管理后台多维度排序。
> 问题：原来用 MySQL ORDER BY 三字段排序，50 万订单数据 filesort 慢查询 2 秒超时。
> 方案：改成查出数据后在 Java 内存用 List.sort() + Comparator 链式排序，SQL 只走索引查数据不排序。
> 效果：响应时间从 2 秒降到 200ms，QPS 提升 3 倍。

---

## 算法分类速查表

### 一、排序算法（6种）

| 序号 | 算法 | 时间复杂度 | 核心思想 | 项目实战场景 |
|------|------|-----------|---------|-------------|
| 1 | 快速排序 | O(nlogn) | 选基准值，小于放左大于放右，递归拆分 | Arrays.sort()底层；复合规则内存排序；缓存数据榜单排序 |
| 2 | 冒泡排序 | O(n²) | 相邻元素两两比较，最大值冒泡到末尾 | 面试必考基础；小数据量(<10)近乎有序时比快排更高效 |
| 3 | 插入排序 | O(n²) | 类似整理扑克牌，逐个插入已排序部分 | Arrays.sort()小数组切换插入排序；流式数据在线排序 |
| 4 | 堆排序 | O(nlogn) | 建大顶堆，取堆顶放末尾，缩堆重复 | Top-K问题(PriorityQueue)；定时任务调度；线程池DelayedWorkQueue |
| 5 | 业务复合排序 | O(nlogn) | List.sort() + 自定义Comparator | 多维度组合排序（状态+金额+时间）；减轻数据库filesort压力 |
| 6 | 归并排序 | O(nlogn) | 双指针合并两个有序列表 | 分库分表跨表有序数据合并；大批量报表导出排序 |

### 二、搜索算法（5种）

| 序号 | 算法 | 时间复杂度 | 核心思想 | 项目实战场景 |
|------|------|-----------|---------|-------------|
| 7 | 二分查找 | O(logn) | 每次取中间值对比，舍弃一半数据 | 按月分表定位子表；有序流水号快速检索；报表时间段定位 |
| 8 | 双指针 | O(n) | 两个指针标记数组两端，一次遍历完成 | 有序数组合并；时间段数据过滤；批量数据快速去重 |
| 9 | 滑动窗口 | O(n) | 固定窗口大小，滑动时只增减边界数据 | 网关/SDK限流统计；监控QPS/流量峰值；连续区间指标统计 |
| 10 | DFS深度优先 | O(V+E) | 沿一条路走到底，回退换路继续 | 文件目录递归遍历；组织树深度遍历；微服务依赖链路追踪 |
| 11 | BFS广度优先 | O(V+E) | 逐层扩展，先访问相邻再下一层 | 社交网络好友推荐(最短关系链)；组织架构层级展示；消息广播 |

### 三、分治算法（2种）

| 序号 | 算法 | 时间复杂度 | 核心思想 | 项目实战场景 |
|------|------|-----------|---------|-------------|
| 12 | 递归 | O(n)~O(2ⁿ) | 方法调用自身，必须设终止条件 | 部门树/菜单树/权限树递归组装；JVM方法调用栈 |
| 13 | 分治 | O(nlogn) | 大问题拆分为相同小问题，分别求解后合并 | 大批量数据分片处理防OOM；分库分表数据合并统计 |

### 四、贪心算法（1种）

| 序号 | 算法 | 时间复杂度 | 核心思想 | 项目实战场景 |
|------|------|-----------|---------|-------------|
| 14 | 贪心算法 | O(nlogn) | 每步选局部最优，推出整体最优 | 优惠券最优抵扣；服务器资源分配；商品满减组合计算 |

### 五、回溯算法（1种）

| 序号 | 算法 | 时间复杂度 | 核心思想 | 项目实战场景 |
|------|------|-----------|---------|-------------|
| 15 | 回溯算法 | O(2ⁿ)/O(n!) | 试探+回退，不满足条件回退换路径 | 权限组合枚举；促销方案组合枚举；任务排期方案 |

### 六、动态规划（1种）

| 序号 | 算法 | 时间复杂度 | 核心思想 | 项目实战场景 |
|------|------|-----------|---------|-------------|
| 16 | 动态规划 | O(n) | 空间换时间，保存计算结果避免重复运算 | 阶梯价格计算；报表累计统计缓存；积分阶梯兑换 |

### 七、哈希算法（1种）

| 序号 | 算法 | 时间复杂度 | 核心思想 | 项目实战场景 |
|------|------|-----------|---------|-------------|
| 17 | 哈希去重 | O(n) | 利用HashSet元素唯一特性一行去重 | 批量ID/手机号去重；报表剔除重复订单；SDK过滤重复请求 |

### 八、设计算法（1种）

| 序号 | 算法 | 时间复杂度 | 核心思想 | 项目实战场景 |
|------|------|-----------|---------|-------------|
| 18 | LRU缓存 | O(1) | 最近最少使用淘汰，访问/写入移到队头 | Guava/Caffeine本地缓存；Redis内存淘汰策略；MyBatis二级缓存 |

### 九、预处理算法（1种）

| 序号 | 算法 | 时间复杂度 | 核心思想 | 项目实战场景 |
|------|------|-----------|---------|-------------|
| 19 | 前缀和 | 预处理O(n) 查询O(1) | 预算前缀和数组，区间和=前缀差 | 报表区间金额统计；股票涨跌区间计算；差分数组区间批量更新 |

### 十、图论算法（1种）

| 序号 | 算法 | 时间复杂度 | 核心思想 | 项目实战场景 |
|------|------|-----------|---------|-------------|
| 20 | 拓扑排序 | O(V+E) | 入度为0的入队，Kahn算法BFS实现 | CI/CD编译模块依赖排序；课程先修关系排课；Spring Bean初始化顺序 |

---

## 速度排序（牢记）

```
O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(2ⁿ) < O(n!)
```

**大白话理解**：
- **O(1)**：直接给你答案，不用找（数组下标取值）
- **O(logn)**：每次砍一半（二分查找，1024条数据最多10次）
- **O(n)**：从头到尾扫一遍（for 循环遍历）
- **O(nlogn)**：扫一遍 + 每次砍一半（快速排序、归并排序）
- **O(n²)**：两两层嵌套循环（冒泡排序，100条数据要比10000次）
- **O(2ⁿ)**：每多一个数据量翻一倍（回溯穷举，20个数据要100万次）
- **O(n!)**：排列组合全试一遍（全排列，10个数据要360万次）

---

## 一眼判断代码复杂度

| 代码特征 | 复杂度 | 大白话 |
|---------|--------|--------|
| 无循环、直接取值 | O(1) | 一步到位 |
| 单层 for/while 循环 | O(n) | 扫一遍 |
| 循环每次折半（二分） | O(logn) | 每次砍一半 |
| 两层嵌套循环 | O(n²) | 扫两遍 |
| 分治排序（快排） | O(nlogn) | 扫一遍+砍一半 |
| 递归无剪枝穷举 | O(2ⁿ) 或 O(n!) | 穷举所有可能 |

---

## 线上优化万能思路

| 序号 | 场景 | 优化方案 | 大白话 |
|------|------|---------|--------|
| 1 | 双重循环 O(n²) | → HashMap 哈希表优化为 O(n) | 与其两层循环找配对，不如把一个列表存进 HashMap，另一个列表查一下就出 |
| 2 | 全量遍历查找有序数据 | → 二分查找 O(logn) | 数据有序就别从头找了，每次看中间砍一半 |
| 3 | 多表有序数据合并排序 | → 分治 + 双指针归并 | 两个排好队的合一个，两边各出一个人比一比 |
| 4 | 单位时间流量统计、限流 | → 滑动窗口减少重复计算 | 窗口移一格，只加新的减旧的，别全部重算 |
| 5 | 重复计算相同子问题 | → 动态规划空间换时间 | 算过的记下来，下次直接查表别重算 |
| 6 | 大数据量取 Top-K | → 堆排序维护小顶堆 | 维护一个大小为 K 的堆，比堆顶大才进去 |
| 7 | 区间和频繁查询 | → 前缀和预处理 O(1) 查询 | 提前算好累加和，区间和 = 前缀差 |