並べ替えられていないデータを含む配列があり、検索には線形検索または二分検索のいずれかを選択する必要があるとします。次に、どのオプションを選択する必要がありますか？線形検索の時間計算量は O(n) で、二分検索は O(log n) です。ただし、最速の並べ替えアルゴリズムでは、O(n * log n) の時間計算量が得られます。さて、2 つのアルゴリズムの複雑さを「追加」する方法がわかりません (それが正しい言葉である場合)。したがって、この質問をしています。
だから私の質問は、ソートしてからバイナリ検索を行う方が単純な線形検索よりも優れているのか、それともその逆なのかということです。
さらに、big O表記を使用して、どのような場合でも証明するにはどうすればよいですか（時間の複雑さを「追加」および「比較」することを意味します）？
読んでいただきありがとうございます!!! それは多くのことを意味します。
複雑さを実際に「追加」することはありません。おっしゃる通り、ソートはO(n * log n)、検索はO(log n)です。それらに対して「通常の計算」を行うと、(n+1)*log n になりますが、これは依然として n*log n です。
そのような複数のステップを実行している場合、通常、最も複雑なものを取り上げてそれを呼び出します。結局のところ、n が十分に大きい場合、n*log n は log n を小さくします。
このように考えてください: n が 1,000,000 の場合、n*log n は 2,000 万です。log n は 20 です。では、20,000,000 と 20,000,020 の違いは何でしょうか? (log n) 項は関係ありません。したがって、(n log n) + (log n) は、すべての意図と目的において、(n log n) に等しくなります。n が 100 の場合でも、log n は 7 です。(log n) 項は、n が適度に大きい場合でも違いはありません。
特定のケースで、リストを 1 回だけ検索する必要がある場合は、順次検索が適しています。複数回検索する必要がある場合は、m 回の検索 O(m * n) のコストと、並べ替えと検索のコストを比較検討する必要があります。最小時間に関心があり、リストを検索する回数がわかっている場合は、(m*n) が (n * log n) より小さい場合は順次検索を使用します。それ以外の場合は、並べ替えを使用してから二分探索を使用します。
しかし、考慮すべき点はそれだけではありません。並べ替えられたリストでの二分検索では応答時間が非常に短くなりますが、線形検索では 1 つのアイテムに非常に長い時間がかかる場合があります。プログラムの起動時にリストを並べ替える余裕がある場合は、プログラムが動作するとアイテムが見つかる (または見つからない) 速度がはるかに速くなるため、おそらくそれが最善の方法です。リストを並べ替えると、応答時間が短縮されます。操作中に非常に予測不可能な応答時間を経験するよりも、起動時に並べ替えの代償を支払う方が適切です。または、思ったよりも多くの検索を行う必要があることがわかります。. .
1 つの検索を実行する必要がある場合は、線形検索を実行します。ソートしてから二分探索するよりも明らかに優れています。
ただし、複数の検索クエリがある場合は、ほとんどの場合、最初に配列を並べ替えてから、すべてのクエリにバイナリ検索を適用する必要があります。
なんで ？O(k) 個の検索クエリを実行するとします。線形検索を行うと、O(n*k)操作になります。最初にソートすると、O(nlogn) + O(klogn) = O((n+k)logn)操作が必要になります。何が良いですか？k が非常に小さい (logn より小さい) 場合は、線形検索を行う方が適切です。ただし、ほとんどの場合、最初にソートすることをお勧めします。
だから私の質問は、並べ替えとバイナリ検索が単純な線形検索よりも優れているかどうかです
はい、あなたは正しいです。
配列が既にソートされている場合は、バイナリ検索を適用する必要があります。そうしないと、バイナリ検索を使用できません。大量のクエリがある場合は、最初に配列をソートしてから、バイナリ検索を適用することをお勧めします。ただし、クエリが数個しかない場合は、線形検索で十分かもしれません。
ビッグ O 表記については、常に「大きい」部分です。つまり、ソートして二分探索すると、O(n*lgn) になります。線形検索だけを使用する場合、それは O(n) です。ただし、クエリの数 (m) を考慮すると、最初のアプローチは O(n*lgn + m*lgn) になり、2 つ目のアプローチは O(m*n) になります。m が大きい場合 (m=n または m>>n)、2 番目のアプローチは二分探索よりも複雑になることがわかります。