git diff 对比一个 10000 行的源文件改动，几毫秒就出结果。背后是 Eugene Myers 1986 年发表的 diff 算法——时间复杂度 O((n+m)·d)，d 是差异行数。几乎所有现代 diff 工具（git、VS Code、GitHub、Beyond Compare）底层都是它。
先看朴素思路：LCS
对比两段文本最直接的思路：找最长公共子序列（LCS）。LCS 里的行就是没变的，其余就是 +/- 的差异。
动态规划解 LCS：构建一个 (n+1) × (m+1) 的二维表，时间和空间都是 O(n·m)。
问题：
- 两个 10000 行文件：1 亿次运算，内存 800 MB
- 实际中 绝大多数行都没变（d 很小），这种浪费就不合理了
Myers 的核心思路：在编辑图上找最短路径
把比较两个序列变成图搜索：
- 构造一个 (n+1) × (m+1) 的网格
- 从 (0,0) 走到 (n,m)
- 每一步有三种走法：
- 向右（→）：删除 A 的一行
- 向下（↓）：插入 B 的一行
- 对角线（↘，仅当 A[i]==B[j]）：两行相同，“免费”走
- 目标：找到走法里 → 和 ↓ 总次数最少的路径，这个次数就是编辑距离 d
关键洞察：如果 d 很小，根本不需要遍历整个网格——从 (0,0) 做广度优先搜索，只需要探索 d 层。
复杂度为什么是 O((n+m)·d)
- 每一层扩展新状态，状态数和 d 成线性
- 每次扩展沿对角线”滑到不能滑为止”
- d = 0（完全相同）时，算法瞬间返回
- d 小（改动少）时，算法几乎不工作
这就是为什么 git diff 大多数时候很快——代码仓库里的改动总是小改动。
还有什么在用 Myers
- git / mercurial / svn 的 diff 引擎
- GNU diff 命令
- VS Code 的行级对比
- Beyond Compare、WinMerge 的底层
- DiffMatchPatch 库（Google 开源）
- LLM 的输出 diff（比如代码修改建议的展示）
局限性：行粒度太粗
Myers 算法本身是按行比较的。如果一行改了一个字符，整行被标记”删 + 加”：
- const x = 100;
+ const x = 200;要在字符级别高亮”100→200”，需要再跑一次 Myers（或 patience diff、histogram diff），对这两行做字符级对比。这就是 GitHub 上”行内 highlight”背后的技术。
改进版本：Patience diff
2008 年提出，git 的 --patience 选项。适用于 Myers 结果”不符合直觉”的情况，比如大段相似代码里的小改动：
- Myers 可能把一对公共空行匹配成”锚点”
- 导致 diff 输出里两块真正相关的代码被拆散到不相邻位置
Patience 先找出唯一共同行作为锚点，在锚点之间递归应用 Myers。生成的 diff 往往更接近程序员的直觉。
实际对比测试
- 相同文件：Myers < 1ms
- 每行都改了（最坏情况 d = n+m）：退化到 O((n+m)²)，10000 行需要 1 秒
- 改动 100 行：几毫秒，和文件大小几乎无关
所以对比历史版本（改动少）很快，对比无关的两个文件反而慢——这是算法本身的特性决定的。
实时对比
粘贴两段文本，逐行 / 逐字符差异高亮、同步滚动、可选忽略空白/大小写——底层就是 Myers 算法的高效实现。