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について、 nの関数としてツリーの深さdを決定します。

    また、 nが無限大に近づくにつれて、ノードごとに平均していくつのブランチ/子があるかを判断します。これは平均分岐係数bと呼ばれます。

  3. 平均分岐係数bで深さdのツリー内のすべてのノードにアクセスするには、少なくともb ^ d操作のオーダーが必要であることを認識してください。その図をnで書くと、入力サイズの複雑さの下限があります。

具体的には、空の文字列をヒットするまで繰り返し、毎回1文字ずつ削除します。文字列の長さをmとnと呼ぶ場合、ツリーの深さはmin（m、n）です。リーフを除くコールツリーのすべてのノードで、正確に3回再帰するため、制限では平均分岐係数は3になります。これにより、Θ（3 ^ min（m、n））ノードのコールツリーが得られます。最悪のケースはm = nのときに発生するため、これをΘ（3 ^ n ）と呼ぶことができます。

これはまだ複雑さの下限にすぎません。全体像を把握するには、再帰呼び出しの間に行われる作業量も考慮する必要があります。この素朴なコードでは、ほとんどすべてを（Θ（n）コストで）コピーする必要があるため、実際には線形時間であり、Θ（n 3 ^ n）全体が複雑になります。*a[:-1]a

[*私はかつてPythonのスライスをバイナリ検索で使用しているCS教授を捕まえましたが、その結果、時間Θ（n lg n）で実行されました。]

于 2013-01-31T15:14:00.403 に答える