並べ替え、選択、検索などのより高度なアルゴリズムのいくつかを理解することで、いくつかの優れたブレークスルーがありました。
ただし、これが私が立ち往生しているシナリオです。
k番目に小さい要素を見つけたい値の配列では、ソートされていない場合はquickselectを使用し、ソートされている場合はバイナリ検索を使用できます。
私の理解が正しければ、ピボット/パーティション システムを介して、quickselect は、ピボットを選択することでソートされていないデータ セットを検索し、各要素をピボットと比較して低値と高値のグループを作成し、変更によってリストを再帰的にサブリストに分解します。ピボット。
これはバイナリ検索の仕組みと非常によく似ているように思えますが、なぜクイックセレクトはソートされていない値に対して機能し、バイナリ検索は機能しないのでしょうか。多くの...コスト？
二分探索はk番目に小さい要素を決定しません。これは選択アルゴリズムではありません。二分探索は、入力として指定した値が配列内にあるかどうかを判別します。
選択アルゴリズムは、k番目に小さい要素を決定します。二分探索の場合のように、配列がすでにソートされている場合、kを配列のインデックスとして使用するだけで、 O(1)でk番目に小さい要素を選択できます。
要約すると、quickselect を使用すると、たとえば配列内で 8 番目に小さい要素を特定できますが、バイナリ検索を使用すると、値 15 の要素が配列内にあるかどうかを検索できます。
Quickselect は、予想されるO(n)時間で任意の順序の統計を選択できます。二分探索はO(log n)時間で要素を検索できますが、配列をソートする必要があります。そうしないと、アルゴリズムが正しくなくなります。先ほど言ったように、並べ替えられた配列でk番目に小さい要素を選択するのは簡単で、並べ替えられた配列のk番目の要素にアクセスするにはO(1)の時間が必要です。
最後に、配列がソートされていないときに要素 (指定された値) を検索するには、配列の線形スキャンを実行する必要があるため、最悪の場合O(n)の時間が必要です。