1

私はアルゴリズムの中級レベルです。最近、さまざまな並べ替えアルゴリズムを比較していたときに、このことが頭に浮かびました。

データがすでに存在するのではなく、入ってくるときに、さまざまな並べ替えアルゴリズムをどのように比較しますか?

私は自分でいくつかを比較しましたが、それが正しいアプローチであるかどうかはよくわかりません.

Insertion Sort : 名前自体が示すように、O(n^2) の複雑さの問題に対する優れた解決策を提示します。

Heap Sort : この手法は、プッシュされたデータ項目ごとにヒープを構築することです。これは、O(logn) の複雑さを持つシフトアップ操作に対応し、最初の要素を最後の要素と交換し、Heapify してヒープ プロパティを復元します。Heapify も O(logn) なので、全体的な複雑さは O(n logn logn) です。ただし、すべてのデータ項目が既に存在する場合、ヒープを構築した後、データ項目に対して Heapify 操作のみを実行しているため、O(n logn) しかありません。

選択並べ替え: 並べ替えの前にすべてのデータ項目が必要なので、選択並べ替えを使用して問題を解決する方法はないと思います。

ツリー ソート: この手法の主要なステップは、最悪の場合の時間計算量が O(n^2) であるツリーを構築することです。そして、順序通りのトラバーサルで十分です。

他のアルゴリズムについてはよくわかりません。

これらのソート手法を完全に把握したいので、この質問を投稿しています。私の質問または私の比較のいずれかに不一致が見つかった場合は、ご容赦ください。

4

2 に答える 2

1

一度に 1 つのアイテムをヒープに構築しても、複雑さが増すことはありO(n log n log n)ません (そして、私にはまったく意味がありません)。実際、ヒープを構築する通常の方法は、一度に 1 つのアイテムをヒープに追加することです。つまり、最初にすべてのアイテムを利用できる場合でも、最初の 2 つのヒープを構築することから始め、次に 3 つ目、4 つ目、というように追加します。一度に1つずつ商品を受け取る場合、余分な作業はまったく発生しません。いつものように、O(N log N) になります。

明確にするために、アイテムを最初の位置に交換してからツリーに移動するのは、アイテムを追加するときではなく、アイテムを削除するときです。つまり、すべてのアイテムをヒープに挿入し終わったら、ソートされた出力を生成するために読み取ります。これを行うには、ヒープのベース (つまり、配列の最初のアイテム) にあるアイテムを配列の末尾にスワップし、配列の末尾から始まるアイテムを取得して、ヒープの上方に移動します。ヒープ プロパティが復元されるまで。

新しいアイテムをヒープに追加するときは、最後に追加してから下に移動してヒープ プロパティを復元します。それらがすべて既に利用可能である典型的なケースでは、配列の先頭から開始し、ヒープを形成するアイテムと、まだごちゃごちゃになっているアイテムとの間にパーティションを作成することによってそれを行います。すべてのアイテムをヒープに構築するには、そのパーティションを 1 つのアイテムに移動し、そのアイテムが属する場所に移動し、繰り返します。すべてのデータをすぐに利用できない「オンライン」バージョンでは、アイテムをヒープに移動した後、次のアイテムが到着するのを待ってからヒープに移動する必要があるだけです (ここで通常は次の項目をすぐに挿入します)。

ツリーの構築は、1) アイテムが完全に注文された状態で到着し、2) それを認識していない場合、および 3) ツリーを構築するときにツリーのバランスを取り直さない場合にのみ、O(N 2 ) になります。アイテムが最初からかなりランダムな順序である場合、バランスを取っていなくても、複雑さは O(N log N) に近くなります。Red-Black や AVL ツリーのようなものを構築する典型的なケースでは、アイテムが順番どおりであっても、O(N log N) のままになります (ただし、アイテムが到着した場合は、より低い定数で O(N log N) になります)。並べ替えではなく、ほぼランダムな順序で)。同様に、B ツリーを使用すると、データが順番どおりに到着したとしても、O(N log N) の複雑さが得られます。

于 2013-07-15T07:32:14.323 に答える
0

Insertion Sort : 名前自体が示すように、O(n^2) の複雑さの問題に対する優れた解決策を提示します。

どちらの場合も、それほど素晴らしいことではありません。

Heap Sort : この手法は、プッシュされたデータ項目ごとにヒープを構築することです。これは、O(logn) の複雑さを持つシフトアップ操作に対応し、最初の要素を最後の要素と交換し、Heapify してヒープ プロパティを復元します。Heapify も O(logn) なので、全体的な複雑さは O(n logn logn) です。ただし、すべてのデータ項目が既に存在する場合、ヒープを構築した後、データ項目に対して Heapify 操作のみを実行しているため、O(n logn) しかありません。

最小ヒープ バイナリ ツリーでこれを行うことができますが、配列を使用している場合、これは難しい場合があります。

選択並べ替え : 並べ替えの前にすべてのデータ項目が必要なので、選択並べ替えを使用して問題を解決する方法はないと思います。

どちらにしてもひどい。

ツリー ソート : この手法の主要なステップは、最悪の場合の時間計算量が O(n^2) のツリーを構築することです。そして、順序通りのトラバーサルで十分です。

基数ソートを使用する場合は O(nlogn)。配列に関するヒープ ソートのコメントを参照してください。

その他の並べ替え:
カウント並べ替え: 事前にデータを把握していないと大変なことになります。どれだけのスペースが必要なのか、実際にはわからないからです。

基数ソート: それでも驚くべきことですが、どちらの場合でも最適なソート アルゴリズムになります。特にバイトソートで行う場合。データが入ってきたらヒストグラムに入力し、それを一時リンクリストに保存するだけです。その後、基数ソートを実行します。

バケット ソート: どちらの方法でも実行できます。カウント ソートよりもはるかに優れていますが、基数ソートほどではありません。

于 2013-07-15T06:37:20.480 に答える