O（n）未満の文字列で文字を検索する

Question

O（n）未満の文字列内の文字を検索することは可能ですか？私が遭遇したアルゴリズムのほとんどは、O（n）時間かかる。 string :: find（）はO（N * M）をとります。文字列全体をトラバースする必要がないアルゴリズムはありますか？

Answer 1

まずは、問題の線形O（n）時間の複雑さよりもアルゴリズムが少ないとは言いません。

もちろん、ラスベガスの考え方のようなランダム化アルゴリズムを試すことができます。あなたのチャーを見つけたら幸運なことに、あなたの配列からランダムな場所を選んでください。

最悪のケースは線形検索のようなものですが、最初に数回試してみると純粋に幸運です。この種のアルゴリズムはおそらくあなたが探しているものです。平均的には、charがもっと速いかもしれませんが、確かにk <がまだ線形時間であるときにk回の試行が必要かどうかを覚えておいてください。 O（k）は

、あなたの入力からより多くを知っている場合多分あなたは違っそれを解決する方法を考えることができます。

希望します。