tsu*_*dot 8 dynamic-programming time-complexity lcs
考虑2个序列X [1..m]和Y [1..n].记忆算法将在时间O(m*n)内计算LCS.有没有更好的算法来找出LCS时间？我想对角完成的memoization可以给我们O(min(m,n))时间复杂度.
Gene Myers在1986年提出了一个非常好的算法,在这里描述:一个O(ND)差分算法及其变化.
该算法需要与序列之间的编辑距离成比例的时间,因此当差异很小时,它会快得多.它的工作原理是循环遍历所有可能的编辑距离,从0开始,直到找到可以构造编辑脚本(在某些方面是LCS的对偶)的距离.这意味着如果差异超过某个阈值,您可以"提前纾困",这有时很方便.
我相信这个算法仍然在许多diff实现中使用.