计算Levenshtein编辑距离的复杂性

Question

我一直在看这个简单的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/

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

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

谢谢.

Answer 1

1. 绘制调用树(您显然已经完成了).

2. 摘要从调用树.对于任意n,确定树的深度d作为n的函数.

   此外,当n接近无穷大时,平均确定每个节点有多少个分支/子节点; 这称为平均分支因子b.

3. 实现访问具有平均分支因子b的深度为d的树中的每个节点至少采用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的切片捕获了CS教授,结果在时间Θ(n lg n)中运行.