如果你有长度为
m
的n
个二进制字符串,是否有更快的方法来确定任意一对之间的最小汉明距离,而不是比较所有O(n^2)
对并计算它们的汉明距离?除了其他事情和下面的评论,汉明距离是一个适当的距离函数,因此满足三角不等式,这让我觉得应该有更快的解决方案。那么,是否可以在少于O(n^2m)
的时间内完成呢?
d(a,c) ≤ d(a,b)+d(b,c)
,这可以确保不必测试每一对。 - Jean-Baptiste Yunès(n-1)*n/2
,因为汉明距离是在两个字符串之间定义的。在这样的汉明空间中进行高效的最近邻搜索并不容易。至少到目前为止,我的谷歌搜索还没有收到有效的结果。 - Axel Kemperm
值)使用查找表来确定两个字符串之间的距离。这将导致复杂度为O(n log n)
。 - Axel Kemper