未分類配列のバイナリ検索の時間の複雑さ

2つの時間の複雑さに悩まされています。ソートされた配列でバイナリ検索を行うにはO（logN）です。ソートされていない配列を検索するには、最初にソートする必要があります。そうすれば、O（NlogN）になります。だから、私たちはO（N）として複雑さを与えるバイナリ検索を実行できますが、O（NlogN）である可能性があると読んでいます。どちらが正しい？未分類配列のバイナリ検索の時間の複雑さ

出典

2013-04-09 user1521306

これらは2つの別々の操作です。バイナリ検索は常に** O（log n）**になります。 – squiguy

2進検索は並べ替えられていない配列に対しては機能しません。ただし、バイナリ検索を実行するには、まず配列をソートする必要があります。少なくとも私は最近学んだ方法です。 – user2373448

バイナリ検索は、「ソート済み」リストです。複雑さはO（logn）です。

「ソートされていない」リストのバイナリ検索は機能しません。これらのリストの場合、最初の要素から順に検索します。これはO（n）の複雑さを与える。 MergeSortまたは他の任意のO（nlogn）アルゴリズムで配列をソートする場合、複雑さはO（nlogn）になります。

O（LOGN）< O（n）の< O（nlogn）

出典

2013-04-09 21:31:55 LuiNova

配列が少しでも並べ替えられていない場合でも、BinarySearchは動作します。注意するのは良いことです。 – ofarooq

あなたの質問への答えはあなたの質問自体にあります。最初にリストをソートしています。クイックまたはマージソートを使用してリストをソートすると、複雑さはo（n log n）になります。パート1が終わる。バイナリ検索を実行する第2の部分は、「ソートされたリスト」で行われます。バイナリ検索の複雑さはo（log n）です。したがって、最終的にプログラムの複雑さはo（n log n）のままです。ただし、配列の中央値を計算する場合は、リストをソートする必要はありません。線形検索やシーケンシャル検索を簡単に適用すると、その検索に役立ちます。

出典

2013-12-02 18:19:03 yuvrajm

リニア検索の時間複雑度はO(n)であり、バイナリ検索の精度はO(log n)（logbase-2）です。ソートされていない配列があり、このためにバイナリ検索を使用する場合は、まず配列をソートする必要があります。そしてここでは配列をソートして要素を検索する時間を費やすのにO(n logn)という時間を費やす必要があります。

出典

2016-11-19 06:37:31

未分類配列のバイナリ検索の時間の複雑さ

答えて

関連する問題