中央値を見つけるためのクイックソート？

Question

最悪のシナリオ$ mathcal {o} left（n^2 right）$は、Quicksortを使用して数字の中央値を見つけるのになぜですか？

• あなたのアルゴリズムが継続的により大きいまたは小さい数を選択した場合 すべて リスト内の数字はあなたのアルゴリズムが失敗しませんか？たとえば、数字のリストが次の場合：

  $ s =（12,75,82,34,55,15,51）$

  また、サブリストを作成するために、$ 82を超える$ 82を超える$ 12を超える数字を選択し続けますが、セットは常に同じサイズのままではありませんか？

• アルゴリズムが$ 1 $のサブリストを作成する数字を継続的に選択した場合、なぜ最悪のシナリオ$ mathcal {o} left（n^2 right）$ですか？それによると、効率は線形ではありません マスター定理, 、$ d> log_b a $？*（したがって、$ mathcal {o} left（n^d right）$またはこの場合は特に$ mathcal {o} left（n right）$）

*ここで、$ d $は効率の指数（つまり線形、指数など）であり、$ b $は各反復で問題のサイズが縮小され、$ a $はサブ問題の数、$ k $はレベルです。フル比：$ t（n）= mathcal {o} left（n^d 右） *（ frac {a} {b^d}）^k $

Answer 1

QuickSortはソート用であり、あなたが参照するアルゴリズムは、 クイック選択.

• リストにある数字をピボットとして選択できるため、1つは発生しません。
• 最悪のケースは、リストを2つのリストに分割する番号を継続的に選択することです。1つの要素と$ n-1 $要素を持つリストだけのリストと、各反復の場合は単一の要素のみを除外します。

したがって、最初の反復$ n $操作、2回目の反復$ n-1 $操作、3番目の1つの$ n-2 $操作、... last Iteration 1操作。

それは最初の$ n $ natural数の合計です：

$ 1+2+3+...+（n-2）+（n-1）+n = n（n-1）/2 $ operations = $ o（n^2）$