3

私は以下のようなブルー​​トフォース文字列パターン検索アルゴリズムを持っています:

public static int brute(String text,String pattern) {
 int n = text.length();    // n is length of text.
 int m = pattern.length(); // m is length of pattern
 int j;
 for(int i=0; i <= (n-m); i++) {
    j = 0;
    while ((j < m) && (text.charAt(i+j) == pattern.charAt(j)) ) {
       j++;
    }
    if (j == m)
     return i;   // match at i
  }
  return -1; // no match
} // end of brute()

ここで上記のアルゴリズムを分析している間、著者は最悪のケースと平均的なケースに言及しました。

私は最悪のシナリオのパフォーマンスを理解しましたが、平均して、作成者はどのようにしてO(m + n)のパフォーマンスを実現しましたか?ここで助けが必要です。

最悪の場合、ブルートフォースパターンマッチングは時間O(mn)で実行されます。

通常のテキストのほとんどの検索の平均はO(m + n)を取りますが、これは非常に高速です。

より平均的なケースの例:T:「文字列検索の例が標準です」P:「ストア」

お時間を割いていただきありがとうございます

4

2 に答える 2

1

彼が で言及しているのO(m+n)は、通常の場合に発生する部分一致です。

たとえば、通常のケースでは次のようになります。

T: "a string searching example is standard" 
P: "store"

反復:

 O(38 + 5) == 43
 a -     no match (1)
 space - no match (2)
     s     - match (3)
     t     - match (4)
     r     - no match (5)
 t     - no match (6)
 r     - no match (7)
 i     - no match (8)
 n     - no match (9)
 g     - no match (10)
 space     - no match (11)

等...

わかりやすくするために、内側のループをインデントしました。

最終的に、すべてが でmあることを確認しましたが、部分一致は、すべてがである(完全な一致が見つかった) か、少なくとも文字数と等しい十分な文字数(部分一致のみ)O(m)を確認したことを意味します。nO(n)n

全体として、これはO(m+n)平均的な時間につながります。

最良のケースはO(n)、一致が の最初にある場合ですm

于 2013-03-22T06:39:32.540 に答える
0

最悪の場合、ブルートフォースパターンマッチングは時間O(mn)で実行されます。

通常のテキストのほとんどの検索の平均はO(m + n)を取りますが、これは非常に高速です。

同じアルゴリズムに対して2つのBig-Oを使用することはできないことに注意してください。

ブルートフォースウィンドウシフトアルゴリズムを適用しているようですが、

時間=(m-n + 1)m

最悪の場合は、m = 1、O(nm)の場合です。

最良のケースは、m = n、Ω(m)の場合です。

于 2013-03-22T07:00:31.160 に答える