クイックソート アルゴリズムを検討しています，パーティション関数のピボットは、配列内の 3 つの (一様に) ランダムに選択された項目の中央値として選択されます。平均的なケースの実行時間を知っている人はいますか?
1405 次
1 に答える
0
小さな仮定：すべての要素が異なります。
この仮定では、ピボットを単なるランダム要素として選択した場合でも、平均実行時間はO（n * log n）です。最も楽観的なシナリオもO（n * log n）です。3つのランダムな要素の中央値を選択しても、平均的なケースが悪化することはないため、O（n * log n）でなければなりません。中央値を見ることで得られるのは、平均からの偏差が小さいことです。クイックソートのそのようなバージョンは、より不運な冗長性があります。
要素が異なる必要がない場合は、すべてが等しい場合を考えてみてください。アルゴリズムがO（n * log n）時間でも機能する場合は、おそらくすべて同じです。
于 2013-03-15T10:47:05.490 に答える