バイナリ検索はO（log n）かO（n log n）ですか？

O（log n）だった時刻とO（n log n）だった時刻に遭遇しました。これは非常に人気のあるインタビューの質問です。したがって、インタビュアーが盲目的にバイナリ検索の実行時間（コンテキストなし）を尋ねると、あなたは何を言うべきですか？バイナリ検索はO（log n）かO（n log n）ですか？

2016-05-14 tnecniv

バイナリ検索で複雑さがO（n log n）の例を挙げることができますか？それを複数回使用することは複雑さには含まれません。場合は、リンクされたリストまたはこれのような何かについては、なぜ誰もリニア検索の代わりにバイナリ検索を使用すると思いますか？ – AbcAeffchen

O（log n）（平均と最悪の場合）誰かがそれがO（n log n）であると主張したことを聞いたことはありません

2016-05-14 14:53:00 zworda

アレイのすべての要素に対してバイナリ検索を行う必要があるときは、n * log n回になることがあります。これは、単一のログnバイナリ検索よりも頻繁に行います。 – tnecniv

バイナリ検索はすべての要素を検索するのではなく、HashMapまたはSetにすべてのデータを配置し、コストをO（n）とし、各要素のコストO（1）で検索します。コストはO（n）.... –

文脈がないので、おもしろい質問のように聞こえます。インタビュアーがバイナリ検索が良い場合とそうでない場合をカバーしたいと思うように見えます。

バイナリ検索は、要素のリストをソートして単一要素を検索した場合に便利です。そのような場合は、O(logn)が必要です。

ここで、ソートされた配列がない場合、ソートするコストはO(n logn)であり、最初のケースを適用できます。そのような場合は、値をセットまたはマップに配置してから検索するとよい（実行時間はO(n)、挿入の場合はO(1)となります）。

いずれの場合も、単一の検索に依存します。バイナリ検索は、単一実行（または、n/2要素、n/4、またはlogn要素のように、nに応じて任意の数の要素を検索するためのものではありません。そのような場合には、より良い方法（セットとマップ）があります。

2016-05-14 19:50:29

答えて