算法与数据结构
复杂度分析与算法设计
共 38 篇
- 001入门算法分析基础：两段代码差在哪以「同算 1 加到 100，一个瞬间一个卡三秒」引入，用真实计时实验建立大 O 直觉：时间与空间两本账、五级复杂度阶梯、最好/最坏/平均与 Ω/Θ 记号、给代码判复杂度的读法，本模块以 Python 为教学语言。
- 002入门数组与动态数组：下标从 0 开始的原因以「arr[i] 为什么是 O(1)」引入：连续内存与寻址公式、插入删除的搬家代价、list 扩容的均摊分析实测、缓存局部性的第二重红利，双指针与滑动窗口技巧预告、前缀和完整示例与遮代码自检。
- 003中级排序算法：从 O(n²) 到 O(n log n)以「给 10 万条成绩单排序」引入：先写出能跑的冒泡与插入排序，实测理解为什么插入排序是 O(n²) 里的实用冠军；再亲手实现归并与快排两个 O(n log n) 主力，用决策树论证比较排序下界，讲透稳定性与自定义比较器，最后看 LC-56/179/315 三个真实应用与七个高频坑。
- 004进阶进阶与线性排序排序算法进阶篇：堆排序（Williams 1964，最坏 O(n log n) 且原地）、希尔排序（Shell 1959，首个突破 O(n²)）、计数/基数/桶三种线性时间非比较排序的适用条件与实验，内省排序（Musser 1997）、Timsort（Peters 2002）与 pdqsort 的工业级混合方案及 Python/Java/C++ 标准库排序源码分析，数据库外部归并排序与 MapReduce TeraSort 工程实践。
- 005入门栈与队列：限制位置，反而更强大以「代码检查器要配对括号」引入：用 list 当栈亲手解括号匹配，理解 LIFO 与调用栈、递归的关系；deque 与循环队列解决假溢出，调度场算法求值表达式，两个栈拼一个队列的均摊分析，单调栈与单调队列的 O(n) 魔法，以及五个高频坑。
- 006中级搜索算法搜索（Search）算法的通用篇：形式化定义、状态空间图模型、完备性与最优性证明，线性搜索 O(n)、二分搜索 O(log n)、哈希查找 O(1)、BFS/DFS 图搜索 O(V+E) 的原理、实现与对比分析，附 Python/C++/Java 多语言实现与 CLRS 第 22 章。有信息搜索与博弈搜索已拆分至 055 篇。
- 007入门启发式搜索与博弈树双向 BFS、IDDFS、A*、IDA* 与 Minimax/Alpha-Beta：利用额外信息加速搜索与对抗决策
- 008中级链表：改两根指针，不搬家以「播放列表频繁插歌删歌」引入：亲手把单链表建出来，用实测看清按位访问的代价，掌握哨兵节点、三指针反转、快慢指针三大技巧，双链表与 LRU 缓存、环形链表与约瑟夫问题，以及链表六大坑。
- 009中级哈希表：为什么 in set 快千倍兑现 010 篇埋下的种子：实测 list 与 set 查找的千倍差距，打开 hash 的黑盒，手写链地址法迷你哈希表并自动扩容，开放寻址与删除标记的陷阱，负载因子与均摊扩容，Redis 渐进式 rehash 与一致性哈希，布隆过滤器等概率亲戚。
- 010中级树：留住顺序，代价是每步一次选择以「哈希表快但没顺序」引入：亲手建二叉树并跑四种遍历，理解递归结构与栈/队列的迭代化，二叉搜索树的查找插入删除与退化实验，自平衡家族（AVL/红黑/B+ 树/LSM）的取舍地图，Trie 前缀树与自动补全，以及验证 BST 的经典 bug。
- 011中级堆与优先队列堆（Heap）与优先队列（Priority Queue）的完全二叉树数组表示、最大堆/最小堆的堆序性质、上浮与下沉操作、Floyd 建堆 O(n) 证明、堆排序、Top-K 问题、索引堆、二项堆、Fibonacci 堆、配对堆的对比分析，涵盖 Williams 1964 Algorithm 232 Heapsort、Floyd 1964 Algorithm 245 Treesort、Vuillemin 1978 二项堆、Fredman-Tarjan 1984 Fibonacci 堆等历史脉络，附 Python/C++/Java 多语言实现与 CLRS 第 6 章。
- 012进阶平衡树与高级树二叉搜索树（BST）、AVL 树（Adelson-Velsky-Landis 1962《An algorithm for the organization of information》Dokl. Akad. Nauk SSSR 146:263-266）、2-3 树（Hopcroft 1970）、红黑树（Bayer 1972 原始版对称二叉 B 树；Guibas-Sedgewick 1978《A Dichromatic Framework for Balanced Trees》FOCS 19th Annual Symposium 现代版；Sedgewick 2008 Left-Leaning Red-Black BST）、B 树（Bayer-McCreight 1972《Organization and Maintenance of Large Ordered Indexes》Acta Informatica 1(3):173-189）、B+ 树（Knuth 1973 TAOCP Vol.3 系统化；Comer 1979《The Ubiquitous B-Tree》Computing Surveys 11(2):121-137）、Splay 树（Sleator-Tarjan 1985《Self-Adjusting Binary Search Trees》JACM 32(3):652-686 DOI:10.1145/3828.3835）、Treap（Seidel-Aragon 1996）、AA 树（Andersson 1993）的形式化定义、旋转操作、平衡不变式与摊还分析、复杂度证明，覆盖 MySQL InnoDB B+ 树聚簇索引 / Linux CFS 红黑树 / Java TreeMap / C++ std::map / PostgreSQL B-tree 等工业案例，附 Python / C++ / Java 多语言实现。
- 013中级图算法：表示与遍历图的形式化定义与四种表示方法（邻接矩阵、邻接表、边集数组、隐式图）对照，BFS 与 DFS 的完整实现、Loop Invariant 正确性证明与预期输出，连通分量、环检测、二分图判定、拓扑排序概念、强连通分量与双连通性，附遍历应用场景速查表、工程实践与五个工业级案例研究；最短路径与最小生成树的三算法双算法横向对照见姊妹篇 115。
- 014进阶最短路与最小生成树图最短路径三算法（Dijkstra、Bellman-Ford、Floyd-Warshall）与最小生成树双算法（Kruskal、Prim）的横向对照篇：松弛操作、堆优化 Dijkstra 的 Python/C++/Java 完整实现与贪心选择性质证明、负权失效反例、Bellman-Ford 与 SPFA 的负环检测、Floyd-Warshall DP 状态设计与正确性概要、A* 启发式搜索、Cut 性质下的 Kruskal 与 Prim 对照实现，附稠密图、稀疏图、负权、多源场景的选型决策表；单算法纵向深水见 250-FloydWarshall 与 260-KruskalAlgorithm。
- 015中级分治算法分治（Divide and Conquer）算法的形式化定义、三步范式（分解-解决-合并）、递推关系 T(n) = aT(n/b) + f(n) 与主定理（Master Theorem, Bentley-Haken-Saxe 1980）三种情况的完整证明、分治与递归的关系、归并排序（von Neumann 1945 EDVAC）、快速排序（Hoare 1961）、Karatsuba 大整数乘法（Karatsuba-Ofman 1963 Soviet Physics-Doklady 7:595-596）、Strassen 矩阵乘法（Strassen 1969 Numerische Mathematik 13(4):354-356）、快速傅里叶变换 FFT（Cooley-Tukey 1965 Mathematics of Computation 19:297-301）、最近点对（Bentley-Shamos 1976）的原理、实现与对比分析，涵盖 von Neumann 1945 EDVAC、Karatsuba 1960 莫斯科大学研讨会、Cooley-Tukey 1965 IBM Watson、Strassen 1969 突破 O(n³)、Bentley-Haken-Saxe 1980 主定理的历史脉络，附 Python/C++/Java 多语言实现与 CLRS 第 2/4/7 章。
- 016中级贪心算法贪心（Greedy）算法的形式化定义、贪心选择性质与最优子结构、拟阵理论（Edmonds 1971）统一框架、交换论证/保持领先/势能下降三大正确性证明方法、活动选择、哈夫曼编码（Huffman 1952）、Kruskal 最小生成树（Kruskal 1956）、Prim 最小生成树（Prim 1957）、Dijkstra 单源最短路（Dijkstra 1959）、分数背包、任务调度、区间调度的原理、实现与对比分析，涵盖 Huffman 1952 MIT、Kruskal 1956 Proc. AMS、Prim 1957 BSTJ、Dijkstra 1959 Numerische Mathematik、Rado 1957、Edmonds 1971 Mathematical Programming 的历史脉络，附 Python/C++/Java 多语言实现与 CLRS 第 16/23/24 章。
- 017中级递归与回溯递归（Recursion）的形式化定义、递归三要素（基线条件/递归条件/状态收缩）、递归树模型与主定理回顾、尾递归优化（TCO）、记忆化递归（Memoization）、回溯算法（Backtracking, Golomb-Baumert 1965 JACM 12(4):516-524）的系统化模板（选择-递归-撤销）、子集/排列/组合/N 皇后（Bezzel 1848）/数独/分割/括号生成/单词搜索的原理、实现与剪枝优化（排序剪枝/边界剪枝/条件剪枝/记忆化剪枝/位运算剪枝）、分支限界法（Land-Doig 1960）与 Dancing Links（Knuth 2000）的原理、对比分析与工程实践，涵盖 McCarthy 1960 LISP 递归系统化、Golomb-Baumert 1965 回溯法、Tarjan 1972 DFS、Bezzel 1848 N 皇后、Land-Doig 1960 分支限界、Knuth 2000 Dancing Links 的历史脉络，附 Python/C++/Java 多语言实现与 CLRS第4/22章、Kleinberg-Tardos第5章。
- 018进阶字符串算法字符串匹配的形式化定义（模式串在主串中的出现位置搜索）、KMP/Boyer-Moore/Rabin-Karp/Sunday/Z 函数等单模式匹配、Aho-Corasick 多模式匹配、后缀数组（倍增/DC3/SA-IS 线性算法）、后缀自动机（endpos 等价类）、后缀树（Ukkonen 线性算法）以及字符串动态规划（LCS、编辑距离、最长回文）的系统化讲解，覆盖复杂度证明、多语言实现（Python/C++/Java）。
- 019中级动态规划（方法论与线性 DP）动态规划方法论与线性 DP 进阶参考书（参考层）：Bellman 最优性原理与最优子结构、重叠子问题、无后效性的形式化定义，状态、转移、初始化三要素方法论，状态数乘转移数的复杂度公式、滚动数组优化、循环不变式正确性论证与伪多项式复杂度，从暴力递归到记忆化搜索到自底向上递推的完整推演，覆盖爬楼梯、打家劫舍、股票买卖系列、最大子数组和、零钱兑换、最长公共子序列、最长递增子序列、编辑距离等线性 DP 经典问题，附 Python/C++/Java 多语言实现与预期输出；背包、区间、树形、状压、数位 DP 见姊妹篇 DP 经典模型进阶。
- 020进阶DP 经典模型进阶动态规划经典模型进阶参考书（参考层）：背包问题家族（0-1、完全、多重、分组）完整实现与选型对比，区间 DP 通用框架与合并石子、矩阵链乘法、戳气球，树形 DP 与没有上司的舞会、打家劫舍 III、二叉树最大路径和，状态压缩 DP 概念级入门（位运算集合编码与 TSP，深水内容见动态规划状态压缩），数位 DP，滚动数组、单调队列、斜率优化、四边形不等式等优化技术总览，延伸至生物信息学序列比对、Viterbi 解码、期权定价、序列推荐的工程实践与 LLVM、PostgreSQL、BLAST、Git 的案例研究，附 Python/C++/Java 多语言实现与预期输出。
- 021入门二分查找家族与变体左右边界、旋转数组、二分答案、插值查找与斐波那契查找——二分家族的纵向深水
- 022中级并查集并查集（Disjoint Set Union, DSU / Union-Find）数据结构的形式化定义、路径压缩与按秩合并的均摊复杂度分析（反 Ackermann 函数 α(n)）、Kruskal 最小生成树/连通分量/冗余连接等典型应用，附 Python/C++/Java 多语言实现。
- 023进阶线段树线段树数据结构的形式化定义（区间幺半群上的完全二叉树）、懒标记下传语义、构建 O(n)、查询/更新 O(log n)、空间 O(4n) 的复杂度证明，覆盖递归/迭代实现、动态开点、离散化、持久化、合并线段树、李超树、扫描线等工程变体，附多语言实现。
- 024中级树状数组树状数组（Fenwick Tree / Binary Indexed Tree, BIT）的形式化定义（基于二进制分解的前缀和索引结构）、lowbit 位运算原理、单点更新 + 区间查询 O(log n)、区间更新 + 单点查询（差分树状数组）、区间更新 + 区间查询（双树状数组）三种模式的形式化推导与复杂度证明，覆盖 Peter M. Fenwick 1994《A New Data Structure for Cumulative Frequency Tables》Software: Practice and Experience 24(3):327-336 DOI:10.1002/spe.4380240306 的历史脉络、lowbit 不变式证明、与线段树 / 平方分解 / 前缀和的对比、Lucene 倒排索引 / Redis Sorted Set / PostgreSQL 统计信息等工业案例，附 Python / C++ / Java 多语言实现。
- 025中级跳跃表跳跃表（Skip List）数据结构的形式化定义（多层索引概率结构）、期望 O(log n) 查找/插入/删除的随机化分析、与平衡树的对比、Redis Sorted Set / LevelDB MemTable / Apache Lucene 倒排索引等工程实现，附多语言实现。
- 026中级布隆过滤器布隆过滤器（Bloom Filter）：一种空间高效的概率数据结构，由 Burton H. Bloom 1970《Space/Time Trade-offs in Hash Coding with Allowable Errors》Communications of the ACM 13(7):422-426 DOI:10.1145/362686.362692 提出。利用 k 个独立哈希函数将元素映射到 m 位的位数组，实现 O(k) 时间复杂度的成员查询，无假阴性但允许可控假阳性。本章涵盖 Bloom 原始动机、假阳性率 P = (1 - e^(-kn/m))^k 的完整推导、最优哈希函数个数 k_opt = (m/n)ln 2 的极值分析、Counting Bloom Filter（Fan et al. 1998 USENIX Summary Cache）、Compressed Bloom Filter（Mitzenmacher 2002）、Cuckoo Filter（Fan et al. 2014 ACM TOCT）、Spectral Bloom Filter、Stable Bloom Filter 等变种；对比 Hash Set、Skip List、HyperLogLog、Cuckoo Filter 的空间/时间/精度权衡；附 Python/C++/Java 三语言实现、工业级应用（Cassandra、HBase、PostgreSQL、Chrome、Bitcoin SPV、Squid Proxy、Bigtable）。
- 027进阶KMP 字符串匹配Knuth-Morris-Pratt（KMP）字符串匹配算法：基于模式串自身结构构建部分匹配表（PMT/next 数组），实现 O(n+m) 线性时间匹配。涵盖 Morris 1970、Pratt 1970 独立发现与 Knuth 1970 复杂度证明的演进脉络，Knuth-Morris-Pratt 1977《Fast Pattern Matching in Strings》SIAM J. Comp. 6(2):323-350 DOI:10.1137/0206024 系统化发表；Cook 1971 字符串匹配下界、Aho-Corasick 1975 多模式扩展、Boyer-Moore 1977、Rabin-Karp 1987、Sunday 1990 变种对比；KMP 在 GNU grep、ESLint、IDE 语法检查、生物信息学 read 比对、Linux 内核字符串搜索中的应用；附 Python/C++/Java 多语言实现与 KMP 自动机、AC 自动机扩展。
- 028进阶动态规划状态压缩状态压缩动态规划（Bitmask Dynamic Programming）：以二进制位编码子集状态，将指数级状态空间压缩至 O(2ⁿ · n) 的可处理范围。系统化梳理 Bellman 1957《Dynamic Programming》Princeton University Press 开山之作、Held-Karp 1962《A Dynamic Programming Approach to Sequencing Problems》J. SIAM 10(1):196-210 DOI:10.1137/0110015 旅行商问题（TSP）O(n² 2ⁿ) 算法、bitmask DP 系统化方法，覆盖 TSP、N 皇后、数独、划分等和子集、棋盘覆盖、排列型 DP 五大经典问题，含位运算技巧（`& | ^ ~`、`<< >>`、`__builtin_popcount`、低比特 `x & (-x)`、子集枚举 `(sub - 1) & S`）、与记忆化递归、自底向上 DP、滚动数组的对比，附 Python/C++/Java 多语言实现与 LeetCode 1879/1655/1494/1125/1931 经典题解，及在 Google OR-Tools、CP-SAT 求解器、Concorde TSP 求解器中的工业级应用。
- 029中级Floyd-Warshall 算法Floyd-Warshall 多源最短路径算法：Robert W. Floyd 1962《Algorithm 97: Shortest Path》CACM 5(6):345 DOI:10.1145/367766.368168 与 Stephen Warshall 1962《A Theorem on Boolean Matrices》JACM 9(1):11-12 DOI:10.1145/321105.321107 独立提出的动态规划算法，Bernard Roy 1959 更早发现传递闭包版本。算法以 O(n³) 时间、O(n²) 空间求解所有顶点对最短路径，支持负权边（无负环），可用于负环检测与传递闭包计算。本文涵盖 DP 状态设计、最优子结构证明、路径重建、位运算优化、与 Dijkstra/Bellman-Ford/Johnson 算法的对比、在 OSPF 路由协议与 NetworkX 工业级库中的应用，附 Python/C++/Java 多语言实现。
- 030中级Kruskal 算法Kruskal 最小生成树算法：Joseph B. Kruskal 1956《On the Shortest Spanning Subtree of a Graph》Proceedings of the American Mathematical Society 7(1):48-50 DOI:10.1090/S0002-9939-1956-0078686-7 提出的贪心加边算法，与 Prim 1957、Jarník 1930、Borůvka 1926 共同构成 MST 算法家族。算法以 O(E log E) 时间、O(V) 空间求解连通无向加权图的最小生成树，借助并查集（Tarjan 1975 路径压缩+按秩合并）实现高效的环检测。本文涵盖贪心选择性质证明、切割性质与回路性质、与 Prim/Borůvka 算法的对比、最小生成森林/次小生成树/TSP 2-近似应用、NetworkX 与 Boost Graph Library 工业级实现，附 Python/C++/Java 多语言实现。
- 031中级拓扑排序拓扑排序（Topological Sort）算法：Arthur B. Kahn 1962《Topological Sorting of Large Networks》Communications of the ACM 5(11):558-562 DOI:10.1145/368996.369025 提出的入度法（Kahn 算法/BFS），与 Robert Endre Tarjan 1972《Depth-First Search and Linear Graph Algorithms》SIAM Journal on Computing 1(2):146-160 DOI:10.1137/0201010 给出的 DFS 后序逆序线性时间算法共同构成两大主流方案。Donald E. Knuth 在《The Art of Computer Programming, Volume 1: Fundamental Algorithms》§2.2.3 系统化讨论拓扑排序与计算机科学中的等价问题。本文涵盖 DAG（有向无环图）的形式化定义、Kahn 与 DFS 算法的正确性证明、与强连通分量（Tarjan 1972）及关键路径法（CPM, Kelly-Walker 1957；PERT, Malcolm-Roseboom-Clark-Fazar 1959）的关系、编译器依赖分析、Make/Build 系统、课程先修关系、并行任务调度等工业级应用，附 Python/C++/Java 多语言实现。
- 032入门数论与模运算算法GCD、扩展欧几里得、快速幂、素数筛、同余与逆元——以 RSA 直观流程收束
- 033进阶计算复杂性理论可计算性、P/NP 复杂度类、多项式归约、NP 完全性、PCP 定理与近似算法。
- 034入门摊还分析与在线算法聚合/记账/势能三方法、竞争分析与在线算法、数据流模型——对序列与不确定未来做保证
- 035入门随机化算法随机化快排、Fisher-Yates 洗牌、蓄水池抽样、蒙特卡洛与拉斯维加斯——用随机换简单与公平
- 036进阶网络流网络流算法：流网络形式化定义 (G,s,t,c,f)、最大流最小割定理、Ford-Fulkerson 方法 O(E·|f*|)、Edmonds-Karp 算法 O(VE²)、Dinic 算法 O(V²E)、Push-Relabel 算法 O(V²E)/O(V³)、ISAP、最小费用最大流、网络单纯形，覆盖二分图匹配、Project Selection、Image Segmentation、Baseball Elimination、Airline Scheduling 等工程应用，附多语言实现。
- 037中级LeetCode 刷题指南：方法论、路线与面试策略LeetCode 刷题指南（方法论与路线篇）系统化阐述刷题总路线（按题型顺序而非题号推进：哈希与双指针、链表、栈与单调栈、二分、滑动窗口与前缀和、二叉树、BFS/DFS、回溯、动态规划、图与贪心）、读题与时间复杂度反推（n ≤ 20 → O(2ⁿ)、n ≤ 100 → O(n³)、n ≤ 10⁵ → O(n log n)）、三遍刷题法与四步解题法、遗忘曲线与间隔重复应对、错题本与复盘指标、周赛/双周赛训练策略、面试流程与沟通话术、工业级代码风格、在线评测平台演进史（ACM ICPC 1970、Google Code Jam 2003-2023、Codeforces 2009、AtCoder 2012、LeetCode 2015/中国 2018）、LeetCode/LintCode/HackerRank/CodeSignal/牛客网五大面试平台对比、FAANG 与字节跳动/腾讯/阿里巴巴面试风格对比、Hot 100/Top Interview 150/Grind 75/NeetCode 150 刷题清单对比、Python/C++/Java 面试语言选择。题型识别信号、解题模板与代表题（双指针/滑动窗口/二分/前缀和/单调栈/哈希/链表/二叉树/BFS-DFS/DP）见本模块《LeetCode 分类题型手册》。
- 038进阶LeetCode 分类题型手册：十大高频题型的识别信号、解题模板与代表题LeetCode 分类题型手册按"识别信号、解题模板、代表题与预期输出"三段式整理十大高频题型：双指针（对撞/快慢指针）、滑动窗口（valid 计数框架）、二分查找（精确匹配/左边界/右边界/旋转排序数组）、前缀和与差分、栈与单调栈、哈希表、链表操作（迭代反转/Floyd 判圈/虚拟头节点）、二叉树递归（后序框架/层序遍历）、BFS 与 DFS（无权图最短路/Kahn 拓扑排序/沉岛/二叉树右侧视图）、动态规划入门（线性 DP/二维 DP/优化链路：暴力→记忆化→迭代→状态压缩），另附回溯与位运算补充模板、七大常见陷阱与修正（二分边界死循环、滑动窗口收缩条件、DP 初始条件、回溯去重、二分 mid 溢出、visited 标记时机、Python 递归栈溢出）及工业应用案例（LC-146 与 Redis LRU/LFU、并查集与 Kubernetes/Git、单调队列与 Prometheus、Trie 敏感词过滤、LC-215 QuickSelect 与 Top-K）。每题模板附 Python 实现与可复现的预期输出，关键模板另附 C++；刷题路线与面试策略见姊妹篇《LeetCode 刷题指南》。