考虑 2 个序列 X[1..m] 和 Y[1..n]。记忆算法将在 O(m*n) 时间内计算 LCS。有没有更好的算法来找出 LCS wrt time？我猜对角线的记忆可以给我们 O(min(m,n)) 时间复杂度。
问问题
12217 次
3 回答
8
Gene Myers 在 1986 年为此提出了一个非常好的算法，在此进行了描述：An O(ND) Difference Algorithm and Its Variations。
该算法所花费的时间与序列之间的编辑距离成正比，因此当差异较小时它会快得多。它通过循环所有可能的编辑距离来工作，从 0 开始，直到找到可以构造编辑脚本（在某些方面是 LCS 的对偶）的距离。这意味着如果差异超过某个阈值，您可以“提前退出”，这有时很方便。
我相信这个算法仍然在许多diff实现中使用。
于 2010-09-10T11:56:02.113 回答
1
如果您先验地知道您关心的最大大小k的上限，您可以通过在内部循环中添加额外的检查来强制 LCS 算法提前退出。这意味着当k << min(m,n)时，尽管您正在执行 LCS，但您可以获得较小的运行时间。
于 2010-06-09T06:21:13.110 回答
0
是的，我们可以创建比 O(m*n) 阶更好的算法——即 O(min(m,n))。找到一个长度.....只需比较对角线元素。每当增量完成时，假设它发生在 c[2,2] 中，然后从 c[2,2++] 和 c[2+] 中增加所有值+,2] 乘以 1.. 直到 c[m,m]..（假设 m
于 2013-12-16T15:20:17.983 回答