ソフト ヒープウィキペディアのページから、最小抽出には一定の時間しかかからないように見えるため、ソフト ヒープを使用してヒープソートを実行すると、償却された O(n) が発生するはずです。定数が大きい場合でも、n が非常に大きい場合、このアルゴリズムは非常に便利です。しかし、私は人々がこれについて言及しているのを聞いたことがありません。人々がこれを使用しない理由はありますか？
ありがとう！
2 に答える
4
@Robのポイントをフォローアップするには：
ヒープソートはその 1 つです。 比較ベースの並べ替えは、平均的なケースでは Ω(n log n) よりも優れたランタイムを持つことはできません。ヒープソートは Θ(n log n) であるため、これは漸近的に最適であり、O(n) 平均時間バリアント (少なくとも、比較ベースのものではない) が存在できないことを意味します。この議論の証明は、情報理論から得られます。少なくとも Ω(n log n) の比較を行わなければ、入力順列を他の入力順列と確実に区別する方法はありません。
ソフト ヒープは、二項ヒープから開始し、ソフト ヒープから n 個の要素を挿入してキューから取り出しても、必ずしもそれらが並べ替えられるとは限らないように、キーの一部を破損することによって発明されました。(ソフトヒープに関する元の論文は、その要約で、構造の創意工夫が格納された値の「エントロピー」を人為的に減少させて、Ω(n log n) バリアを打ち負かすと述べています)。これが、ソフト ヒープが O(1) 時間操作をサポートできる理由です。通常のヒープ構造とは異なり、常にソートされるわけではないため、上記のランタイム バリアに拘束されません。したがって、n 個のオブジェクトを O(n) 時間でソフト ヒープからエンキューおよびデキューできるという事実は、ソフト ヒープを使用してヒープソートを高速化できないことをすぐに示します。
より一般的には、比較ベースのデータ構造を使用してソート アルゴリズムを構築する方法はありません。ただし、そのデータ構造を使用する場合、平均して少なくとも Ω(n log n) の作業を行う必要があります。たとえば、この前の質問では、O(n) 時間でバイナリ ヒープを BST に変換できない理由を説明しています。これを行うと、純粋に比較を使用して O(n) 時間でソートできるためです (O(n) でヒープを構築します)。 ) 時間、次に O(n) 時間で BST に変換し、O(n) 時間で順序通りのトラバーサルを実行して、ソートされたシーケンスを復元します)。
お役に立てれば！
于 2013-06-10T16:44:44.827 に答える