2

私は最近アルゴリズムについて多くのことを学びました、そして検索されたバイナリは大量のソートされたデータの中のアイテムを見つけることにおけるその効率のために歓迎されます。しかし、そもそもデータがソートされていない場合はどうなるでしょうか。どの時点で、バイナリ検索はシーケンシャル検索に対して効率を向上させます。バイナリ検索では、最初に指定された配列をソートしてから検索する必要があります。いくつかの結果を見たいと思う前に誰かがこれをテストした場合、私はバイナリ検索がシーケンシャル検索を通過するポイントを確認することに興味があります。

14個の要素を持つ配列foo[BUFF]が与えられます

1 3 6 3 1 87 56 -2 4 61 4 9 81 7

バイナリ検索では最初に配列を並べ替えてから番号3を検索する必要があるため、たとえば... 3のように、指定された番号を見つけるには順次並べ替えの方が効率的だと思います。

1000個の要素が保持されている配列bar[BUFF]が与えられます

1 2 4 9 -2 3 8 9 4 12 4 56 //continued

私が間違っていなければ、理論的には、ソートしてからバイナリ検索を呼び出す方が効率的です。

4

2 に答える 2

12

情報が知られていないソートされていない配列では、線形時間検索を行う必要があります。

線形時間検索は各要素を 1 回チェックするため、複雑さはO(n)です。それを並べ替えと比較します。各要素を複数回チェックする必要があり、複雑さが のソート アルゴリズムO(n * log n)。そのため、ソートするだけでも、順次検索よりも遅くなります。二分探索はO(log n)、任意に並べ替えられたデータを持っているだけでは、まったく役に立ちません。

ただし、複数回検索する場合は、最初に並べ替えを検討してください。長期的には効率が向上します。

于 2012-12-08T10:36:40.263 に答える
4

複数の検索を行う必要がある場合は、検索する前に並べ替える方が高速になります。単一の要素のみを検索する必要がある場合、並べ替えはいずれにせよすべての要素を検査する必要があるため、並べ替えは遅くなります。

複数の検索を行っている場合は、最初にソートする価値があるかもしれませんが、損益分岐点 (線形検索とプレソート + バイナリ検索の間) は、必要な検索の数、要素の数、ソート アルゴリズムによって異なります。使用され、データがソートされます。

于 2012-12-08T10:35:51.907 に答える