编辑距离（Levenshtein距离）递归自上而下实现的复杂性

I have been working all day with a problem which I can't seem to get a handle on. The task is to show that a recursive implementation of edit distance has the time complexity Ω(2^max(n,m)) where n & m are the length of the words being measured.

该实现与这个小型 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)

From: http://www.clear.rice.edu/comp130/12spring/editdist/ 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。

I would be grateful for any tips on how I can proceed to show that the lower bound complexity is Ω(2^max(n,m)).

你的递归公式：

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)我们只需要计算节点数。

A shortest path has the length min(m,n), so the tree has at least 3min(m,n) nodes. But there are some path that are longer. You get the longest path by alternately reduce the first and the second string. This path will have the length m+n-1, so the whole tree has at most 3m+n-1 nodes.

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

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

So Ω(2max(m,n)) and Ω(3min(m,n)) are lower bounds and O(3m+n-1) is an upper bound.