3

実験結果ではなく、理論的な理由を知りたいです。また、データ サイズが小さいか大きいかを判断するにはどうすればよいでしょうか。

明確に説明しませんでしたが、入力データのサイズが小さい場合、通常、挿入ソートを使用するか、クイック ソートを使用しないかを選択するという意味です。だから私はそれがなぜなのか知りたいのですか？

4

1 に答える 1

16

漸近分析では、定数要因を無視することに注意してください。したがって、クイックソートの O(n log n) の複雑さは、実際には O(C(n log n)) です。ここで、C は未知の定数です。同様に、挿入ソートの O(n^2) は実際には O(C(n^2)) です。これらの定数を Cq と Ci としましょう。

したがって、(Ci * n^2) < (Cq * (n log n)) の場合、挿入ソートは高速になります。

2 つのアルゴリズムを見ると、Ci < Cq であることは明らかです。挿入ソートは信じられないほど簡単です。アルゴリズムは比較とスワップに過ぎず、ループ オーバーヘッドが少し発生します。

クイックソートは少し複雑で、反復ごとにより多くのステップが必要ですが、反復は少なくなります。

5 要素配列の並べ替えを検討してください。最悪の場合、挿入ソートで十分です。

  • 外側のループ制御変数の 5 つのインクリメントと比較
  • 内側のループ制御変数の 15 回のインクリメントと比較
  • 15元素比較
  • 15回のスワップ

ここでQuicksortを見てください。平均的なケースでは、4 つの部分配列を分割する必要があります。5 要素の配列は、3 要素と 2 要素の 2 つのサブ配列に分割されます。3 要素のサブ配列は、さらに 1 要素と 2 要素のサブ配列に分割されます。次に、2 つの 2 要素サブアレイが分割されます。

したがって、このpartitionメソッドは 4 回呼び出されます。各分割ステップでは、要素の比較とスワップ、およびその他のオーバーヘッドに加えて、最低 2 つのスワップが必要です。すべてを合計すると、クイックソートは反復ごとにより多くの作業を行うことがわかります。反復回数が少ない場合、挿入ソートは反復回数が多くても、総作業量は少なくなります。

ステップバイステップの分析を行って、「小さい」という理論値を決定できます。この場合、挿入ソートはクイックソートよりも高速になります。通常、これは「基本操作」をカウントすることによって行われますが、定義は多少柔軟です。この場合は非常に簡単です。比較、代入、または関数呼び出しは「基本操作」です。

理論的な結果が実験的に導き出された結果とどのように一致するかは、特定のコンピューター ハードウェアと、比較にかかる費用によって異なります。比較に非常にコストがかかる場合は、比較回数が最も少ないアルゴリズムを選択する必要があります。ただし、比較が比較的安価な場合 (たとえば、数値を比較したり、長い共通のプレフィックスがない場合は文字列を比較したりする場合)、アルゴリズムのオーバーヘッドが制限要因となり、単純で非効率的なアルゴリズムが複雑で効率的なアルゴリズムよりも優れています。

于 2013-10-28T16:12:05.953 に答える