计算Levenshtein编辑距离的复杂度

Question

我今天一直在研究这个简单的 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/

我知道它的复杂度是指数级的，但我该如何从头开始计算这个复杂度呢？

我在网上搜索了很久，但没有找到任何解释，只有说它是指数级的说法。

谢谢。

Answer 1

1. 画出调用树（你显然已经做过了）。

2. 从调用树中抽象出来。对于任意的 n，找出树的深度 d 和 n 的关系。

   还要找出每个节点平均有多少个分支/子节点，当 n 趋近于无穷大时，这个值叫做平均分支因子 b。

3. 明白在一棵深度为 d、平均分支因子为 b 的树中，访问每个节点至少需要大约 b ^ d 次操作。把这个数字用 n 表示出来，你就得到了输入大小的复杂度下限。

更具体地说：你会一直递归，直到遇到空字符串，每次去掉一个字符。如果我们把字符串的长度叫做 m 和 n，那么树的深度就是 min(m, n)。在调用树的每个节点（除了叶子节点）上，你会递归三次，所以在极限情况下，平均分支因子是 3。这就给我们带来了一个有 Θ(3^min(m, n)) 个节点的调用树。最坏的情况是 m = n，所以我们可以称之为 Θ(3^n)。

这仍然只是复杂度的下限。为了全面了解，你还应该考虑递归调用之间的工作量。在这段简单的代码中，这实际上是 线性时间，因为 a[:-1] 需要复制几乎所有的 a，这使得总复杂度为 Θ(n 3^n)。

[* 我曾经看到一位计算机科学教授在二分查找中使用 Python 的切片，结果运行时间是 Θ(n lg n)。]