0

同じN個の数字の配列があります。それにクイックソートを適用しています。この場合、並べ替えの時間の複雑さはどうあるべきですか。

この質問をぐるぐる回しましたが、正確な説明は得られませんでした。

4

2 に答える 2

0

単純なクイックソート アルゴリズムは になりますO(n^2)。これは、よりスマートなピボット選択アルゴリズムを使用している場合でも当てはまります。を回避するO(n^2)には、クイックソート アルゴリズムで数値をピボットごとに 3 つのセット (より小さい、等しい、より大きい) に分割する必要があります。

よりスマートなピボット選択アルゴリズムは次のとおりです。

  • ヒューリスティックに基づくもの (例: 1 番目の要素、中間要素、および最後の要素から取得された候補ピボットの中央値を選択)
  • 保証に使用されるものO(n log n)- ここでは説明しませんが、このようなアルゴリズムは、ピボットが、たとえば、並べ替えられた配列の 25 ～ 75% からのものであることを保証する場合があります。

ただし、ほとんどの通常のクイックソート アルゴリズムでは、数値がピボットより小さいか大きいかに分割されます。ピボットに等しいものは、ピボットより大きいまたは小さいものと任意にバンドルされます。

すべての数値が等しい場合、各パーティションは 1 つのパーティションのみを生成するため、残りのパーティションのサイズは毎回 1 ずつ減少します。

これを回避するには、クイックソート アルゴリズムで数値を 3 つのセット (ピボットより小さい、大きい、等しい) に分割する必要があります。

于 2012-09-23T01:10:28.897 に答える
0

すべての数値をチェックする必要があるため（純粋なクイックソートを使用する場合）、常に同じカウントの比較が行われます（このような特別なケースをチェックする特別な関数を追加しない限り）。ただし、数値を切り替える必要はないため、これが最良のシナリオです。したがって、複雑さは (n log n) である必要があります。

于 2012-09-18T16:22:38.703 に答える