5

我整天都在看这个Levenshtein Edit Distance的简单 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/

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

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

谢谢。

4

1 回答 1

8

  1. 绘制调用树（您显然已经完成了）。

  2. 调用树的摘要。对于任意n ，将树的深度d确定为n的函数。

    此外，确定每个节点平均有多少个分支/子节点，因为n接近无穷大；这称为平均分支因子b。

  3. 意识到以平均分支因子b访问深度为d的树中的每个节点至少需要b ^ d操作的顺序。用n写出这个数字，就输入大小而言，您的复杂度有一个下限。

更具体地说：你不断递归，直到你碰到一个空字符串，每次去掉一个字符。如果我们将字符串的长度称为m和n，那么树的深度就是 min( m , n )。在调用树中除叶子之外的每个节点处，您恰好递归 3 次，因此在极限情况下，平均分支因子为 3。这为我们提供了 Θ(3^min( m , n )) 节点的调用树。最坏的情况发生在m = n时，所以我们可以称之为 Θ(3^ n )。

这仍然只是复杂度的下限。对于全貌，您还应该考虑递归调用之间完成的工作量。在这个幼稚的代码中，这实际上是线性时间，因为a[:-1]必须复制（以 Θ( n ) 成本）几乎所有aΘ( n 3^ n ) 总复杂度。*

[* 我曾经发现一位 CS 教授在二进制搜索中使用 Python 的切片，结果在时间 Θ( n lg n ) 中运行。]

于 2013-01-31T15:14:00.403 回答