5

私の計算によると：

  • クイックソートのコスト = n + (n/2 + n/2) + (n/4 + n/4 + n/4 + n/4) + ... = n * log(n) = log(n n )
  • ヒープソート コスト = 合計 [log(i)] for i = n, n-1, n-2, ..., 1 = log(n!)

クイックソートはヒープソートよりも定数係数が優れていると言われているため、クイックソートは平均してヒープソートよりも優れているのはなぜですか? log(n n ) > log(n!) じゃない？

4

2 に答える 2

6

以下は、Steven S. Skiena の The Algorithm Design Manual の段落で、3 つの O(nlogn) ソート アルゴリズム間の速度について説明しています。

しかし、2 つの Θ(n log n) アルゴリズムを比較して、どちらが速いかを判断するにはどうすればよいでしょうか?クイックソートが本当に速いことをどのように証明できるでしょうか? 残念ながら、 RAM モデルと Big Oh 分析は、そのような種類の区別を行うには粗すぎるツール セットを提供します。同じ漸近的な複雑さのアルゴリズムに直面した場合、実装の詳細と、キャッシュのパフォーマンスやメモリ サイズなどのシステムの癖が決定的な要因になる可能性があります。

私たちが言えることは、適切に実装されたクイックソートが適切に実装されている場合、通常、マージソートやヒープソートよりも 2 ～ 3 倍高速であることが実験で示されているということです。主な理由は、最も内側のループの操作がより単純になることです。しかし、私がクイックソートの方が速いと言うのを信じないなら、私はあなたに反論することはできません。 これは、私たちが使用している分析ツールの外に解決策がある質問です。判断する最善の方法は、アルゴリズムと実験の両方を実装することです。

-4.6.3 「クイックソートは本当に速いのか?」、アルゴリズム設計マニュアル

于 2013-08-27T01:11:41.377 に答える