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

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) ) 的任何提示，我将不胜感激。

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-13m+n-1

让m = min(m,n). 这棵树还至少包含

不同的路径，每个可能的减少顺序都有一个n。

所以和是下界 和是一个上限。Ω(2max(m,n))Ω(3min(m,n))O(3m+n-1)