クイックソートを乱数化アルゴリズムとランダムに比較する方法

Question

randomize_quicksort()を使用すると、ランダムプロセスでピボットを選択するので、平均ケースの複雑さはO（nlgn）です。しかし、私がをランダムに選んだの選択アルゴリズムでは、randomize_quicksort（）にランダムに類似したピボットを選択すると、最悪の場合O（n^2）の複雑さに終わった。ピボット要素を選択するのと同じ戦略を使用していますが、二次的な時間で実行する要素は何か分かりません。

ありがとうございました

Answer 1

あなたの質問にはすでに回答が含まれています。クイックソートの平均的なケースと、選択アルゴリズムの最悪ケースについて話しています。それは同じことではありません。どちらのアルゴリズムも最悪の場合、二次的です。