阅收藏：有40年历史的算法被证明是最优的

比较两个符号序列相似度的算法“编辑距离”已有40多年的历史。40多年来，计算机科学研究人员一直试图改进这个算法，但毫无所获。在下周举行的ACM Symposium on Theory of Computing会议上，MIT研究人员将发表证明该算法是最优的报告。这可能会让人感到失望，因为这意味着在一台计算机上使用现有的算法去详细比较两个人类基因组的相似度将需要1000年的时间。好的方面是计算机科学家不用再为算法能否改进苦恼了。







via Solidot