5

ランダム化されたクイックソートを実装する2つの方法、

方法1：ランダムピボットを選択する

方法2：入力のランダム順列を生成し、最初の要素をピボットとして選択するクイックソートにフィードします

ランダム化に関して、method1はmethod2と同じですか？

注：Method2はすべてのパーティションを同じように生成するように見えますが、method1は生成しません。したがって、それらが同じでない場合は、パフォーマンスへの影響を理解したいと思います。

4

1 に答える 1

2

はい。いずれの場合も、特定の要素がピボットとして選択される確率は 1/len(input) です。(ただし、2 番目の方法は、ランダム順列を生成するために追加の線形パスが必要になるため、ほぼ確実に定数倍遅くなります。)

于 2013-02-13T22:13:48.223 に答える