ボイヤームーアアルゴリズムの前処理時間はΘ（m + |Σ|）で、マッチング時間はΩ（n / m）、O（n）です。ボイヤームーア文字プールは、簡略化されたボイヤームーア文字自体の進歩であると理解していますが、このWikipediaの記事によると、平均的なケースの複雑さはO（N）であり、最悪のケースはO（MN）です。したがって、最悪の場合、ボイヤームーアアルゴリズムよりも遅くなるはずです。しかし、チリ大学によるこの古典的な調査は、ボイヤームーア文字のhorspoolがボイヤームーア文字をほぼ毎回上回っていることを示しています。私は混乱しています！文字列検索に（小さいパターンと大きいパターンの両方で）どちらを使用する必要がありますか？また、実際の世界でより重要なアルゴリズムはどれですか（私はコンピュータサイエンスの学生です）。
2137 次
1 に答える
4
キーワードは「ほぼ」です。最悪の場合の動作は、ごく少数のケースで発生する可能性があります。実生活での平均的な行動と漸近的な行動も、かなりゆるく結びついています。Boyer-Moore-Horspoolの最良の動作は、Boyer-Mooreの場合と同じです。ボイヤー-ムーア-ホースプールの最悪のケースは、ボイヤー-ムーアよりもかなり悪いです。通常の使用では、Boyer-Moore-HorspoolはBoyer-Mooreとほぼ同じになる傾向がありますが、オーバーヘッドと初期化のコストが少し良くなります（低くなります）。
どちらを使用しますか？それはあなたの目標とあなたが検索されるパターンとテキストの方法であなたが何を期待するかに依存します。どちらも実装するのは特に難しいことではないので、両方を実行して結果を自分で比較してみませんか。（あなたが学生であることを認めるとどうなるか見てみましょう？あなたは課題を取得します！:)）
于 2012-07-12T23:35:28.733 に答える