4

Rabin-Karp アルゴリズムの最悪の場合の実行時間が O(nm) であり、平均的な場合が O(n+m) である理由を理解しようとしています。

誰かがそれを手伝ってくれますか？

4

2 に答える 2

5

ウィキは、アルゴリズムの時間の複雑さについてかなりよく説明しています。

ハッシュ演算機能の有効性（計算済みのハッシュ値を一定時間で動的に再利用できる能力と読み替える）は、アルゴリズムの時間計算量を計算する際の決め手と言えます。

ハッシュ計算によってこの違いがどのように生じるかを見てみましょう。

時間計算量はO(nm)、次の場合です。

call hash(s[1..m])                  // O(m) additive
for index from 1 to n-m+1           // O(n)
    //Code to check if substring matches
    call hash(s[index+1..index+m])  // Inefficient hash function, takes O(m), just like naive string matching

に比べてO(nm)、添加物 O(m)はほとんど無視されています。

与える、O(m) + O(n)*O(m)=O(nm)

時間計算量はO(n+m)、次の場合です。

call hash(s[1..m])                  // O(m) additive
for index from 1 to n-m+1           // O(n)
    //Code to check if substring matches
    call hash(s[index+1..index+m])  //Efficient hash function which takes only O(1), applies Rolling Hashing

与える、O(m) + O(n)*O(1)= O(m) + O(n)=O(m+n)

于 2016-09-09T09:39:39.500 に答える
5

Rabin-Karp は最悪のケースO(nm) です。これは、すべてのポイント (そのうちの ) で偽陽性を見つける可能性があり、文字列を実際に比較する必要があるため、一致を確認するためにn最大 までの比較が必要になる可能性があるためです。m

発生してはならない半合理的なハッシュ関数を使用しても、ほとんどすべてのハッシュ関数について、上記の異常な動作を示すクエリ (つまり、検索対象の文字列と部分文字列の両方) を作成することができます。

したがって、RK は O(n) の時間計算量を期待していますが、最悪の場合の時間計算量は O(nm) です。(注:mは より大きくてはならないためn、n + mは で囲まれ2nているため、O(n + m) は O(n) と同じです。)

問題がすべての一致する部分文字列を見つけることである場合、O(nm) 動作を生成する方が簡単です。これは、RK がよく使用される別のコンテキストです。その場合、ソース文字列のすべてのポイントで部分文字列を一致させる必要があるため、m as で構成される文字列内で s で構成される部分文字列を検索するには、n a間違いなく時間がかかります。nm

病理学的なケースであっても、n でまだ線形であるすべての部分文字列を見つけるための他のアルゴリズムが存在します。

于 2016-09-09T17:00:03.217 に答える