我一直在研究这个简单的Python实现编辑距离 http://en.wikipedia.org/wiki/Levenshtein_distance现在一整天。
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)
From: http://www.clear.rice.edu/comp130/12spring/editdist/ http://www.clear.rice.edu/comp130/12spring/editdist/
我知道它具有指数复杂性，但是我将如何从头开始计算该复杂性？
我一直在互联网上搜索，但没有找到任何解释，只是声明它是指数级的。
Thanks.
-
绘制调用树（显然您已经完成了）。
-
从调用树中抽象出来。对于任意n, 确定深度d树的函数n.
另外，确定每个节点平均有多少个分支/子节点，如下所示n接近无穷大；这就是所谓的平均分支因子b.
-
实现访问深度树中的每个节点d具有平均分支因子b至少需要以下顺序b ^ d运营。将该数字写成n并且就输入大小而言，复杂性有一个下限。
更具体地说：您不断递归，直到遇到空字符串，每次删除一个字符。如果我们称字符串的长度为m and n，则树的深度为 min(m, n）。在调用树中除叶子之外的每个节点上，您都精确地递归 3 次，因此在极限情况下，平均分支因子为 3。这给了我们一个 θ(3^min(m, n)) 节点。最坏的情况发生在m = n，所以我们可以称之为 θ(3^n).
这仍然只是复杂性的下限。为了全面了解，您还应该考虑递归调用之间完成的工作量。在这段简单的代码中，实际上是线性时间因为a[:-1]必须复制（在 θ(n）成本）几乎全部a，给出 θ(n 3^n) 总复杂度。*
[* 我曾经发现一位计算机科学教授在二分搜索中使用 Python 的切片，结果运行时间为 θ(n lg n).]
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
