2つのシーケンスX[1..m]とY[1..n]を考えてみましょう。メモ化アルゴリズムは、時間O（m * n）でLCSを計算します。LCS wrt timeを見つけるためのより良いアルゴリズムはありますか？斜めにメモ化すると、O（min（m、n））の時間計算量が得られると思います。
12217 次
3 に答える
8
1986年のGeneMyersは、このための非常に優れたアルゴリズムを考案しました。ここでは、O（ND）差分アルゴリズムとそのバリエーションについて説明します。
このアルゴリズムは、シーケンス間の編集距離に比例して時間がかかるため、差が小さい場合ははるかに高速です。これは、0から始まり、編集スクリプト（ある意味ではLCSのデュアル）を構築できる距離が見つかるまで、すべての可能な編集距離をループすることによって機能します。これは、差がしきい値を超えた場合に「早期に救済」できることを意味します。これは便利な場合があります。
このアルゴリズムはまだ多くのdiff実装で使用されていると思います。
于 2010-09-10T11:56:02.113 に答える
1
気になる最大サイズkの上限が事前にわかっている場合は、内側のループに追加のチェックを追加することで、LCSアルゴリズムを早期に終了させることができます。つまり、k << min（m、n）の場合、LCSを実行しているにもかかわらず、実行時間が短くなる可能性があります。
于 2010-06-09T06:21:13.110 に答える
0
はい、Order O（m * n）---つまりO（min（m、n））よりも優れたアルゴリズムを作成できます。長さを見つけるには.....対角要素を比較するだけです。インクリメントが行われるたびに、c [2,2]で発生したと想定し、c[2,2++]とc[2+からすべての値をインクリメントします。 +、2] 1 ..まで進み、c [m、m] ..まで進みます（mと仮定します
于 2013-12-16T15:20:17.983 に答える