编辑距离（Levenshtein距离）递归自顶向下实现的复杂度

Question

我一整天都在解决一个问题，但似乎无法掌握它。这个任务是展示递归实现的编辑距离具有时间复杂度Ω(2^max(n,m))，其中n和m是被测量单词的长度。

这个实现类似于这个小Python例子：

def lev(a, b):
    if("" == a):
       return len(b)   # returns if a is an empty string
    if("" == b):
        return len(a)   # returns if b is an empty string
    return min(lev(a[:-1], b[:-1])+(a[-1] != b[-1]), lev(a[:-1], b)+1, lev(a, b[:-1])+1)

来源：http://www.clear.rice.edu/comp130/12spring/editdist/

我尝试过为不同的短单词绘制递归深度树，但我找不到树深度和复杂度之间的联系。

我的计算得出的递归公式：

m = length of word1
n = length of word2
T(m,n) = T(m-1,n-1) + 1 + T(m-1,n) + T(m,n-1)
With the base cases:
T(0,n) = n
T(m,0) = m

但是我不知道该如何进行，因为每次调用都会导致3个新的调用，因为长度未达到0。

如果您能提供任何提示，让我如何证明下限复杂度为Ω(2^max(n,m))，我将不胜感激。

- John

---

你对大omega有把握吗？让我们将n保持为常数1。然后，我们可以轻松地看出复杂度是km（树几乎是一个列表），并且很明显km < 2^m = 2 ^ max（1，m）对于 m >= m_0。 - tb-

Answer 1

你的递归公式：

T(m,n) = T(m-1,n-1) + T(m-1,n) + T(m,n-1) + 1
T(0,n) = n
T(m,0) = m

是正确的。

你可以看到，每个 T(m,n) 都分成了三条路径。由于每个节点都在 O(1) 的时间内运行，我们只需要计算节点数。

最短路径的长度为 min(m,n)，所以树至少有 3min(m,n) 个节点。但也有一些更长的路径。通过交替减少第一个和第二个字符串，您可以得到最长的路径。这条路径的长度为 m+n-1，因此整棵树最多有 3m+n-1 个节点。

设 m = min(m,n)。该树还包含至少

不同的路径，每个路径对应于减少 n 的每种可能顺序。

因此，Ω(2max(m,n)) 和 Ω(3min(m,n)) 是下限，O(3m+n-1) 是上限。

- AbcAeffchen