小编Joh*_*ohn的帖子

我一直在看这个简单的Levenshtein编辑距离的 python实现.

def lev(a, b):
    """Recursively calculate the Levenshtein edit distance between two strings, a and b.
    Returns the edit distance.
    """
    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/

我知道它具有指数复杂性,但我将如何从头开始计算这种复杂性？

我一直在互联网上搜索,但没有找到任何解释,只有它是指数的声明.

谢谢.

我一整天都在处理一个我似乎无法解决的问题。任务是证明编辑距离的递归实现具有时间复杂度 Ω(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) …