计算Levenshtein编辑距离的复杂度。

Question

我一整天都在研究这个简单的Python实现的Levenshtein编辑距离。

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/

我知道它具有指数复杂度，但我该如何从头开始计算这种复杂度呢？

我已经在互联网上搜索了很久，但没有找到任何解释，只有说它是指数复杂度的说法。

谢谢。

- John

---

尝试绘制调用树。通常，这可以通过动态规划/备忘录解决。 - nhahtdh

我已经做了这个，但是我找不到节点数量和指数增长之间的联系。 - John

这个天真的实现是指数级的，但算法不必如此。记忆化使其成为多项式级别。 - nneonneo

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]必须复制（以Θ(n)的成本）几乎所有的a，总共给出Θ(n 3^n)的复杂度。*

[* 我曾经发现一位计算机科学教授在二分查找中使用Python的切片，结果运行时间为Θ（n lg n）]。

- Fred Foo

---

谢谢，伙计。那是我见过的最好的问题解释。 - John