如何以低于O(n²m)时间计算n个长度m二进制字符串的最小汉明距离？

当然有！而且你的直觉完全正确——利用汉明距离满足三角不等式的特性，确实能找到远优于暴力O(n²m)的解法。下面我来拆解几种实用的优化思路：

1. 哈希分桶：精准筛选潜在近邻 #

汉明距离的本质是两个二进制串的差异位数，我们可以通过生成“容错变种”哈希来快速定位可能的近邻，避免全量比对：

• 假设我们要找最小汉明距离k，对每个二进制串，生成所有“允许k位翻转”的变种（比如k=1时，对每个位翻转一次，生成m个变种）
• 将这些变种作为键存入哈希表，对应值为原字符串的索引
• 遍历每个原串时，检查它的所有变种在哈希表中是否存在已存入的其他字符串——如果存在，说明这两个串的汉明距离≤k
• 从k=0开始递增检查，第一个找到匹配的k就是全局最小汉明距离

这种方法的时间复杂度约为O(nmk)，当最小k远小于m时，效率比O(n²m)提升几个数量级。

2. 度量空间索引：基于三角不等式的剪枝 #

既然汉明距离满足三角不等式（d(a,c) ≤ d(a,b)+d(b,c)），我们可以用专门的度量空间索引结构来大幅减少比对次数：

• VP树（Vantage Point Tree）：这是为度量空间设计的索引树，构建树的时间为O(n log n)，查询每个点的最近邻时间为O(log n)，整体复杂度可降至O(n m log n)，远低于O(n²m)
• 简易剪枝版：先将所有字符串按汉明重量（1的个数）排序，维护当前最小距离min_dist。遍历每个字符串s_i时，只和后面的s_j比对，一旦d(s_i,s_j) ≥ min_dist就停止后续比对——因为排序后后续串与s_i的距离只会更大，根据三角不等式，它们和其他串的距离也不可能比当前min_dist更小。

3. 位运算加速：把单对计算从O(m)降到O(m/w) #

就算需要做部分比对，也可以用位运算把汉明距离的计算速度拉满：

• 将二进制串转换为整数数组（比如每个元素存储64位，对应CPU字长w）
• 两个串的异或结果中，1的个数就是汉明距离，而计算1的个数可以用CPU内置指令（比如x86的popcnt）或语言内置优化方法（比如Python的bin(x).count('1')）
• 这样单对字符串的汉明距离计算时间从O(m)降到O(m/w)，就算是O(n²)的比对，实际运行速度也会快很多。

如果最小汉明距离很小，哈希分桶是最优选择；如果距离不确定，VP树这类索引结构能稳定将复杂度控制在O(n m log n)；就算是基础比对，位运算加速也能大幅降低实际耗时。这些方法都能轻松超越暴力遍历的O(n²m)复杂度。

内容的提问来源于stack exchange，提问作者Simd