Linux下的diff命令复杂度多少？

你可以到 gnu 官网去下载一份 diffutils 的源码研究，里面包含 diff，cmd 两个命令的实现。

我粗略看过源码，因为 diff 和 cmd 寻找差异都是以行为单位进行比对的，所以跟你想象的 LCS 算法是有区别的。

算法里的核心思路之一是哈希，每一行内容都被哈希成一个数值并放入一个开链式的哈希表中，比对时是从哈希表中快速找出另一个文件中匹配相等的行。

另外内部使用了 LCS 算法的变体，如果没有指定 --minimal，它查找到的结果是接近最优。官方文档里的复杂度介绍：

Unless the --minimal option is used, diff uses a heuristic by Paul Eggert that limits the cost to O(N^1.5 log N) at the price of producing suboptimal output for large inputs with many differences.
当差异非常小时，这里算法的复杂度接近O(N)，并且N为行的数量。执行上，几乎是仅对两个文件扫描一遍的速度，因为从磁盘读文件的时间比往往计算多。