编辑距离的复杂性（Levenshtein距离）递归自上而下实施 [英] Complexity of edit distance (Levenshtein distance) recursion top down implementation

问题描述

我一直在工作了一整天与我似乎无法得到一个手柄上的问题。的任务是要表明，递归执行编辑距离的具有时间复杂＆欧米茄;（2 ^{最大值（N，M）功能}），其中n＆安培;米是被测量的话的长度。

I have been working all day with a problem which I can't seem to get a handle on. The task is to show that a recursive implementation of edit distance has the time complexity Ω(2^max(n,m)) where n & m are the length of the words being measured.

的实施相当于这个小蟒蛇例如

The implementation is comparable to this small python example

def lev(a, b):
    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 /

我曾尝试递归深度绘制树木不同的短的话，但我不能找到树的深度和复杂性之间的连接。

I have tried drawing trees of the recursion depth for different short words but I cant find the connection between the tree depth and complexity.

这是我的计算递推公式

m = length of word1
n = length of word2
T(m,n) = T(m-1,n-1) + 1 + T(m-1,n) + T(m,n-1)
With the base cases:
T(0,n) = n
T(m,0) = m

不过，我不知道如何进行，因为每次调用导致了3个新的呼叫的长度没有达到0。

But I have no idea on how to proceed since each call leads to 3 new calls as the lengths don't reach 0.

我会很感激的，我可以如何进行显示，下界的复杂性和欧米茄任何提示;（2 ​​ ^{MAX（N，M）}）

I would be grateful for any tips on how I can proceed to show that the lower bound complexity is Ω(2^max(n,m)).

推荐答案

您递推公式推

T(m,n) = T(m-1,n-1) + T(m-1,n) + T(m,n-1) + 1
T(0,n) = n
T(m,0) = m

是正确的。

您可以看到，进入三个路径每 T（M，N）分裂。由于每个节点运行 O（1），我们只需要计算节点。

You can see, that every T(m,n) splits of into three paths. Due to every node runs in O(1) we only have to count the nodes.

一个最短路径具有长度分（M，N），所以树至少有 3 分（M，N ） 节点。但也有一些路径是更长的时间。你得到由交替的最长路径减小第一和第二串。这条路径的长度 M + N-1 ，所以整个树有最多 3 M + N-1 节点。

A shortest path has the length min(m,n), so the tree has at least 3min(m,n) nodes. But there are some path that are longer. You get the longest path by alternately reduce the first and the second string. This path will have the length m+n-1, so the whole tree has at most 3m+n-1 nodes.

让的M = min（M，N）。在树中也至少

不同的路径，一个是 N 的降低了每一个可能的顺序。

different paths, one for each possible order of reducing n.

所以Ω（2 MAX（M，N））和Ω（3 分（M ，N））的下限和 0（3 M + N-1 ）是一个上界。

So Ω(2max(m,n)) and Ω(3min(m,n)) are lower bounds and O(3m+n-1) is an upper bound.

这篇关于编辑距离的复杂性（Levenshtein距离）递归自上而下实施的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！