[解決済み】Quickselectの時間の複雑さを説明する

質問内容

から https://en.wikipedia.org/wiki/Quickselect とあります。

しかし、quickselectでは、quicksortのように両側から再帰するのではなく、片側（探している要素がある側）からしか再帰しません。これにより、平均的な計算量は O(n log n) から O(n) に減少し、最悪の場合 O(n^2) になります。

片側だけしか見ないようにすることで、平均複雑度がO(n)に減少することが理解できないのですが？O(N/2 log N)であって、O(N log N)ではないでしょうか？また、最悪の場合、O(n^2)になるのはなぜでしょうか？

どのように解決するのですか？

n log(n) は、アルゴリズムがすべてのN個の項目をlog(n)回見ることを意味します。しかし、Quickselectではそのようなことは起こりません。

例えば、128個のリストから上位8個を選ぶためにQuickselectを使っているとします。そして、奇跡的なランダム選択により、選んだピボットが常に中途半端な位置にあるとします。

最初の反復で、アルゴリズムは全128項目を調べ、64項目ずつの2つのグループに分割する。次の反復では、32個ずつの2つのグループに分割されます。次に16個、そして8個となる。検査されるアイテムの数は

N + N/2 + N/4 + N/8 + N/16

その系列の和が2*Nに達することはない。

最悪のケースは、パーティショニングによって常にパーティションサイズが非常に偏ってしまうことです。もし最初のパーティショニングで1つのアイテムしか削除されなかったらどうなるかを考えてみましょう。そして、2番目の分割では1つだけ、など。その結果、次のようになります。

n + (n-1) + (n-2) ...

というのは (n^2 + n)/2) またはO(n^2)です。