编辑距离（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)