二分探索アルゴリズムはO（log n）の大きなO値を持ち、順次探索はO（n）の大きなO値を持ちます。ただし、二分探索の前に並べ替えアルゴリズムが必要であり、並べ替えアルゴリズムに最適な大きなO値はO（n.log n）です。したがって、事実上、バイナリ検索の大きなO値はO（n.log n）であり、これはシーケンシャル検索の値よりも大きくなります。では、検索アルゴとしてどちらが好ましいですか？
質問する
223 次
2 に答える
3
実際には、検索の頻度によって異なります。何百万回も検索する必要がある場合は、並べ替えの前払い費用を支払わなければならない場合でも、バイナリ検索が必要です。ユースケースによって異なります。バイナリ検索では、挿入によってリストがソートされたままになることも保証されるため、挿入も遅くなります。
多くの挿入を行う必要があり、検索が非常に少ない場合は、順次検索の方が高速になる可能性があります。
大量のデータを処理するまで、これの多くは目立たないことを覚えておいてください。
于 2012-08-27T16:41:24.890 に答える
2
シーケンシャル検索は、最適化されたアプリケーションで実際に使用されることはめったにありません。通常、適切なデータ構造を見つけてから、 O（n）で頻繁に使用される検索を提供するものを使用する方がはるかに優れているためです。
たとえば、赤黒木は、すべてO（log n）で挿入/削除/検索を提供する特殊な種類の平衡二分木です。そのため、作成、入力、検索が高速です。
于 2012-08-28T07:50:37.037 に答える