时间复杂度（Time Complexity）描述算法执行时间随输入规模 n 的增长趋势，空间复杂度（Space Complexity）描述算法额外占用空间随 n 的增长趋势。
复杂度
名称
示例
n=1000 时大致操作数
O(1)
常数
数组按下标访问
1
O(log n)
对数
二分查找
10
O(n)
线性
遍历数组
1000
O(n log n)
线性对数
快排、归并
10000
O(n²)
平方
冒泡、选择
1,000,000
O(2ⁿ)
指数
斐波那契递归
1.07e301
O(n!)
阶乘
全排列
远超宇宙原子数
2.2 复杂度分析的三个原则
原则
说明
示例
只保留最高阶项
低阶项和常数忽略
3n² + 5n + 100 → O(n²)
乘法法则
嵌套循环相乘
双层循环 → O(n²)
加法法则
并列循环相加，取大者
一个 O(n) + 一个 O(n²) → O(n²)
2.3 摊还复杂度（Amortized Complexity）
graph LR
A["第 1 次 push_back\n扩容, O(n)"]
B["第 2~n 次 push_back\n不扩容, O(1)"]
C["第 n+1 次 push_back\n扩容, O(n)"]
D["摊还 = O(1)"]
A --> B --> C --> D
style A fill:#FFB3C6,stroke:#F48FB1,color:#333
style B fill:#B5EAD7,stroke:#80CBC4,color:#333
style C fill:#FFB3C6,stroke:#F48FB1,color:#333
style D fill:#FFF9C4,stroke:#F9A825,color:#333
std::vector 的 push_back 是均摊 O(1)：单次扩容 O(n)，但 n 次扩容总共 O(n)，所以单次均摊 O(1)。这是面试官最爱追问的细节之一。
// 归并排序：稳定，O(n log n) 时间，O(n) 空间 voidmerge(vector<int>& arr, int l, int m, int r){ vector<int> left(arr.begin() + l, arr.begin() + m + 1); vector<int> right(arr.begin() + m + 1, arr.begin() + r + 1); int i = 0, j = 0, k = l; while (i < left.size() && j < right.size()) { if (left[i] <= right[j]) arr[k++] = left[i++]; // <= 保证稳定性 else arr[k++] = right[j++]; } while (i < left.size()) arr[k++] = left[i++]; while (j < right.size()) arr[k++] = right[j++]; }
voidmergeSort(vector<int>& arr, int l, int r){ if (l >= r) return; int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); merge(arr, l, m, r); }
// 快速排序：不稳定，O(n log n) 均值 / O(n²) 最坏，O(log n) 空间（递归栈） intpartition(vector<int>& arr, int l, int r){ int pivot = arr[r]; // 选最右为基准 int i = l - 1; for (int j = l; j < r; ++j) { if (arr[j] <= pivot) { ++i; swap(arr[i], arr[j]); } } swap(arr[i + 1], arr[r]); return i + 1; }
voidquickSort(vector<int>& arr, int l, int r){ if (l >= r) return; int p = partition(arr, l, r); quickSort(arr, l, p - 1); quickSort(arr, p + 1, r); }
快速排序的非递归实现
1 2 3 4 5 6 7 8 9 10 11 12 13
// 快排非递归版：用栈模拟递归 voidquickSortNonRec(vector<int>& arr, int l, int r){ stack<pair<int,int>> stk; stk.push({l, r}); while (!stk.empty()) { auto [left, right] = stk.top(); stk.pop(); if (left >= right) continue; int p = partition(arr, left, right); stk.push({left, p - 1}); stk.push({p + 1, right}); } }
快排的优化：三数取中
1 2 3 4 5 6 7 8
// 三数取中：选左、中、右三个数的中位数作基准，避免有序数组退化 intmedianOfThree(vector<int>& arr, int l, int r){ int m = l + (r - l) / 2; if (arr[l] > arr[m]) swap(arr[l], arr[m]); if (arr[l] > arr[r]) swap(arr[l], arr[r]); if (arr[m] > arr[r]) swap(arr[m], arr[r]); return m; // arr[m] 是三者的中位数 }
// 堆排序：不稳定，O(n log n) 时间，O(1) 空间 voidheapify(vector<int>& arr, int n, int i){ int largest = i; int left = 2 * i + 1, right = 2 * i + 2; if (left < n && arr[left] > arr[largest]) largest = left; if (right < n && arr[right] > arr[largest]) largest = right; if (largest != i) { swap(arr[i], arr[largest]); heapify(arr, n, largest); } }
voidheapSort(vector<int>& arr){ int n = arr.size(); // 建堆（从最后一个非叶节点开始） for (int i = n / 2 - 1; i >= 0; --i) heapify(arr, n, i); // 一个个取出堆顶 for (int i = n - 1; i > 0; --i) { swap(arr[0], arr[i]); // 堆顶最大值放到末尾 heapify(arr, i, 0); } }
3.10 计数排序（Counting Sort）
原理：统计每个值出现的次数，按顺序回填。非比较排序。
1 2 3 4 5 6 7 8 9
// 计数排序：稳定，O(n + k) 时间，O(k) 空间 voidcountingSort(vector<int>& arr, int maxVal){ vector<int> cnt(maxVal + 1, 0); for (int x : arr) cnt[x]++; // 计数 int idx = 0; for (int v = 0; v <= maxVal; ++v) { while (cnt[v]-- > 0) arr[idx++] = v; // 回填 } }
3.11 桶排序（Bucket Sort）
原理：把元素分散到若干桶里，每个桶内部排序，最后合并。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
// 桶排序：稳定，O(n + k) 均值，O(n²) 最坏 voidbucketSort(vector<float>& arr){ int n = arr.size(); vector<vector<float>> buckets(n); // 1. 分桶 for (float x : arr) { int idx = n * x; // 假设输入在 [0, 1) buckets[idx].push_back(x); } // 2. 桶内排序 for (auto& b : buckets) sort(b.begin(), b.end()); // 3. 合并 int idx = 0; for (auto& b : buckets) for (float x : b) arr[idx++] = x; }
3.12 基数排序（Radix Sort）
原理：按位数从低位到高位依次排序（用计数排序作为子过程）。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
// 基数排序：稳定，O(n × k) 时间，k 为最大位数 voidradixSort(vector<int>& arr){ int maxVal = *max_element(arr.begin(), arr.end()); for (int exp = 1; maxVal / exp > 0; exp *= 10) { vector<int> output(arr.size()); vector<int> cnt(10, 0); // 计数 for (int x : arr) cnt[(x / exp) % 10]++; // 前缀和 for (int i = 1; i < 10; ++i) cnt[i] += cnt[i - 1]; // 反向填充，保证稳定性 for (int i = arr.size() - 1; i >= 0; --i) { output[--cnt[(arr[i] / exp) % 10]] = arr[i]; } arr = output; } }
// BFS：用队列实现 voidbfs(vector<vector<int>>& graph, int start){ int n = graph.size(); vector<bool> visited(n, false); queue<int> q; q.push(start); visited[start] = true; while (!q.empty()) { int u = q.front(); q.pop(); cout << u << " "; for (int v : graph[u]) { if (!visited[v]) { visited[v] = true; q.push(v); } } } }
// DFS 递归版 voiddfs(vector<vector<int>>& graph, int u, vector<bool>& visited){ visited[u] = true; cout << u << " "; for (int v : graph[u]) { if (!visited[v]) dfs(graph, v, visited); } }
// DFS 迭代版：用栈 voiddfsIter(vector<vector<int>>& graph, int start){ int n = graph.size(); vector<bool> visited(n, false); stack<int> stk; stk.push(start); while (!stk.empty()) { int u = stk.top(); stk.pop(); if (visited[u]) continue; visited[u] = true; cout << u << " "; for (int v : graph[u]) if (!visited[v]) stk.push(v); } }
// Dijkstra：用优先队列（最小堆）优化 vector<int> dijkstra(vector<vector<pair<int,int>>>& graph, int src){ int n = graph.size(); vector<int> dist(n, INT_MAX); dist[src] = 0; // (距离, 节点) 最小堆 priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq; pq.push({0, src}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; // 过期节点跳过 for (auto [v, w] : graph[u]) { if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } } return dist; }
6.5 Floyd 全源最短路径
1 2 3 4 5 6 7 8 9
// Floyd-Warshall：三层循环 voidfloyd(vector<vector<int>>& dist){ int n = dist.size(); for (int k = 0; k < n; ++k) // 跳板 for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j]; }
6.6 拓扑排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
// 拓扑排序（Kahn 算法，BFS 思路） vector<int> topologicalSort(int n, vector<vector<int>>& graph, vector<int>& indegree){ vector<int> res; queue<int> q; for (int i = 0; i < n; ++i) if (indegree[i] == 0) q.push(i); // 入度为 0 的入队 while (!q.empty()) { int u = q.front(); q.pop(); res.push_back(u); for (int v : graph[u]) { if (--indegree[v] == 0) q.push(v); } } return res.size() == n ? res : vector<int>{}; // 空表示有环 }
// 并查集 structUnionFind { vector<int> parent, rank; UnionFind(int n) : parent(n), rank(n, 0) { iota(parent.begin(), parent.end(), 0); } intfind(int x){ return parent[x] == x ? x : parent[x] = find(parent[x]); } boolunite(int x, int y){ int px = find(x), py = find(y); if (px == py) returnfalse; if (rank[px] < rank[py]) swap(px, py); parent[py] = px; if (rank[px] == rank[py]) ++rank[px]; returntrue; } };
// Kruskal：按边权升序，依次加入不形成环的边 intkruskal(int n, vector<vector<int>>& edges){ sort(edges.begin(), edges.end(), [](auto& a, auto& b){ return a[2] < b[2]; }); UnionFind uf(n); int total = 0; for (auto& e : edges) { int u = e[0], v = e[1], w = e[2]; if (uf.unite(u, v)) total += w; } return total; }
// 方法 1：DFS 遍历 boolisConnectedDFS(vector<vector<int>>& graph){ int n = graph.size(); vector<bool> visited(n, false); dfs(graph, 0, visited); for (bool v : visited) if (!v) returnfalse; returntrue; }
// 方法 2：BFS 遍历 boolisConnectedBFS(vector<vector<int>>& graph){ int n = graph.size(); vector<bool> visited(n, false); queue<int> q; q.push(0); visited[0] = true; int count = 1; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : graph[u]) { if (!visited[v]) { visited[v] = true; ++count; q.push(v); } } } return count == n; }
// 方法 3：并查集 boolisConnectedUF(int n, vector<vector<int>>& edges){ UnionFind uf(n); for (auto& e : edges) uf.unite(e[0], e[1]); int root = uf.find(0); for (int i = 1; i < n; ++i) if (uf.find(i) != root) returnfalse; returntrue; }
// 动态规划解回文子串 string longestPalindrome(string s){ int n = s.size(); if (n < 2) return s; vector<vector<bool>> dp(n, vector<bool>(n, false)); int start = 0, maxLen = 1; // 初始化：单字符回文 for (int i = 0; i < n; ++i) dp[i][i] = true; // 枚举子串长度 for (int len = 2; len <= n; ++len) { for (int i = 0; i + len - 1 < n; ++i) { int j = i + len - 1; if (s[i] == s[j]) { if (len == 2) dp[i][j] = true; else dp[i][j] = dp[i + 1][j - 1]; } if (dp[i][j] && len > maxLen) { start = i; maxLen = len; } } } return s.substr(start, maxLen); }
// 中心扩展法：O(n²) 时间，O(1) 空间（推荐） string longestPalindromeExpand(string s){ int n = s.size(); int start = 0, maxLen = 1; auto expand = [&](int l, int r) { while (l >= 0 && r < n && s[l] == s[r]) { if (r - l + 1 > maxLen) { start = l; maxLen = r - l + 1; } --l; ++r; } }; for (int i = 0; i < n; ++i) { expand(i, i); // 奇数长度 expand(i, i + 1); // 偶数长度 } return s.substr(start, maxLen); }
7.7 编辑距离（Levenshtein Distance）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
// 编辑距离：增删改三操作的最小次数 inteditDistance(string word1, string word2){ int m = word1.size(), n = word2.size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); for (int i = 0; i <= m; ++i) dp[i][0] = i; for (int j = 0; j <= n; ++j) dp[0][j] = j; for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) if (word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1]; else dp[i][j] = 1 + min({ dp[i - 1][j], // 删除 dp[i][j - 1], // 插入 dp[i - 1][j - 1] // 替换 }); return dp[m][n]; }
7.8 DP 题目汇总表
题目
LeetCode
难度
关键点
爬楼梯
70
简单
dp[i] = dp[i-1] + dp[i-2]
打家劫舍
198
中等
状态机 DP
0/1 背包
——
中等
二维降一维
完全背包
——
中等
正序遍历
最长递增子序列
300
中等
二分优化
最长回文子串
5
中等
中心扩展
编辑距离
72
困难
三方向转移
最小路径和
64
中等
网格 DP
最大子序和
53
简单
Kadane 算法
八、字符串匹配算法
8.1 字符串匹配算法对比
算法
预处理
匹配最坏
特点
应用
朴素算法
O(1)
O(mn)
暴力简单
教学
KMP
O(m)
O(n)
利用已匹配信息不回退
文本搜索
BM
O(m + σ)
O(n)
从后往前匹配，跳得多
实际编辑器
Sunday
O(m + σ)
O(n)
比 BM 更简单
日常使用
Rabin-Karp
O(m)
O(n) 均值
哈希滚动
抄袭检测
n 为主串长度，m 为模式串长度，σ 为字符集大小。
8.2 朴素字符串匹配
1 2 3 4 5 6 7 8 9 10
// 朴素匹配：暴力 intnaiveSearch(const string& text, const string& pattern){ int n = text.size(), m = pattern.size(); for (int i = 0; i + m <= n; ++i) { int j = 0; while (j < m && text[i + j] == pattern[j]) ++j; if (j == m) return i; // 匹配成功 } return-1; }
8.3 KMP 算法（必须掌握）
KMP 核心：当匹配失败时，利用已经匹配的信息，让模式串不回退到 0，主串也不回退。关键是 next 数组（部分匹配表）。
KMP 流程
graph TB
A["📝 主串: ABCABABCABC"]
B["🔍 模式串: ABCABC"]
C["i=0, j=0\n比较 A=A ✓"]
D["依次比较\n直到 j=5, text=ABCAB✓, ABCAB"]
E["text[A] ≠ pattern[A]\n主串不回退\n模式串 j 移到 next[5]=2"]
F["继续从 j=2 开始\n匹配成功"]
A --> B --> C --> D --> E --> F
style A fill:#C7CEEA,stroke:#9FA8DA,color:#333
style B fill:#E8D5F5,stroke:#CE93D8,color:#333
style C fill:#B5EAD7,stroke:#80CBC4,color:#333
style D fill:#B5EAD7,stroke:#80CBC4,color:#333
style E fill:#FFB3C6,stroke:#F48FB1,color:#333
style F fill:#B5EAD7,stroke:#80CBC4,color:#333
// Sunday 算法 intsundaySearch(const string& text, const string& pattern){ int n = text.size(), m = pattern.size(); // 记录 pattern 中每个字符最右出现的位置 unordered_map<char, int> shift; for (int i = 0; i < m; ++i) shift[pattern[i]] = m - i; int i = 0; while (i + m <= n) { int j = 0; while (j < m && text[i + j] == pattern[j]) ++j; if (j == m) return i; // 看对齐末尾之后的字符 if (i + m < n && shift.count(text[i + m])) i += shift[text[i + m]]; else i += m + 1; } return-1; }
graph LR
A["头节点"] --> B
B --> C
C --> D
D --> E["环入口"]
E --> F
F --> G
G --> H
H --> E
style A fill:#C7CEEA,stroke:#9FA8DA,color:#333
style E fill:#FFB3C6,stroke:#F48FB1,color:#333
// 删除链表中指定值的节点（头节点也可能被删） ListNode* deleteNodeByValue(ListNode* head, int val){ if (!head) returnnullptr; if (head->val == val) { ListNode* newHead = head->next; delete head; return newHead; } ListNode* prev = head, *cur = head->next; while (cur && cur->val != val) { prev = cur; cur = cur->next; } if (cur) { prev->next = cur->next; delete cur; } return head; }
9.6 两个链表的交点
1 2 3 4 5 6 7 8 9 10 11
// 找两个链表的交点（双指针法） ListNode* getIntersectionNode(ListNode* headA, ListNode* headB){ if (!headA || !headB) returnnullptr; ListNode* pA = headA, *pB = headB; // 走完自己的路走对方的路，最终相遇 while (pA != pB) { pA = pA ? pA->next : headB; pB = pB ? pB->next : headA; } return pA; }
9.7 链表常用操作汇总表
操作
时间复杂度
关键点
反转链表
O(n)
三指针或递归
判断环
O(n)
快慢指针
找环入口
O(n)
快慢指针 + 同步前进
找交点
O(n + m)
双指针或哈希
合并两个有序链表
O(n + m)
哨兵节点
删除倒数第 k 个
O(n)
双指针（间距 k）
判断回文
O(n)
快慢指针 + 反转
十、topK 问题（万数找第 K 大）
10.1 4 种解法对比
解法
时间复杂度
空间复杂度
适用场景
全排序
O(n log n)
O(1)
K 接近 n
冒泡 K 次
O(nK)
O(1)
K 极小（如 K=1, 2）
最小堆（K 大小）
O(n log K)
O(K)
✅ 大文件、海量数据
快速选择
O(n) 均值 / O(n²) 最坏
O(log n)
✅ 内存允许
10.2 最小堆解法
graph TB
A["初始化最小堆\n容量 K"]
B["遍历数组前 K 个\n构建初始堆"]
C["遍历剩余元素"]
D{"当前元素 > 堆顶?"}
E["弹出堆顶\n压入当前元素\n向下调整"]
F["跳过"]
G["遍历结束\n堆顶即为第 K 大"]
A --> B --> C --> D
D -->|"是"| E
D -->|"否"| F
E --> C
F --> C
C -.->|"结束"| G
style A fill:#C7CEEA,stroke:#9FA8DA,color:#333
style B fill:#FFDAB9,stroke:#FFAB76,color:#333
style C fill:#FFDAB9,stroke:#FFAB76,color:#333
style D fill:#FFF9C4,stroke:#F9A825,color:#333
style E fill:#B5EAD7,stroke:#80CBC4,color:#333
style F fill:#F5F5F5,stroke:#999,color:#333
style G fill:#FFB3C6,stroke:#F48FB1,color:#333
1 2 3 4 5 6 7 8 9
// topK：找前 K 大的数（最小堆） intfindKthLargest(vector<int>& nums, int k){ priority_queue<int, vector<int>, greater<int>> minHeap; for (int x : nums) { minHeap.push(x); if (minHeap.size() > k) minHeap.pop(); // 维护堆大小为 k } return minHeap.top(); // 堆顶就是第 K 大 }
graph TB
A["客户端调用 get(key)"]
B{"缓存中存在?"}
C["返回 -1"]
D["取出节点"]
E["移动到链表头"]
F["客户端调用 put(key, value)"]
G{"key 已存在?"}
H["更新值\n移到链表头"]
I{"容量已满?"}
J["淘汰链表尾节点"]
K["插入新节点到头部\n加入哈希表"]
A --> B
B -->|"否"| C
B -->|"是"| D --> E
F --> G
G -->|"是"| H
G -->|"否"| I
I -->|"是"| J --> K
I -->|"否"| K
style A fill:#C7CEEA,stroke:#9FA8DA,color:#333
style C fill:#FFB3C6,stroke:#F48FB1,color:#333
style D fill:#FFDAB9,stroke:#FFAB76,color:#333
style E fill:#B5EAD7,stroke:#80CBC4,color:#333
style F fill:#C7CEEA,stroke:#9FA8DA,color:#333
style H fill:#B5EAD7,stroke:#80CBC4,color:#333
style J fill:#FFB3C6,stroke:#F48FB1,color:#333
style K fill:#B5EAD7,stroke:#80CBC4,color:#333
十二、实战：实现一致性哈希
**一致性哈希（Consistent Hashing）**用于分布式缓存，解决传统 hash(key) % N 在节点增减时几乎全部缓存失效的问题。
// 添加物理节点 voidaddNode(const string& node){ for (int i = 0; i < virtualNodes; ++i) { string vnode = node + "#" + to_string(i); ring[hash(vnode)] = node; } }
// 删除物理节点 voidremoveNode(const string& node){ for (int i = 0; i < virtualNodes; ++i) { string vnode = node + "#" + to_string(i); ring.erase(hash(vnode)); } }
// 找 key 对应的节点 string getNode(const string& key){ if (ring.empty()) return""; int h = hash(key); auto it = ring.lower_bound(h); if (it == ring.end()) it = ring.begin(); // 环形回到起点 return it->second; } };