57

先週、著者が 2 ページ目に言及しているこの論文に出くわしました。

これにより、整数のエッジの重みに対して線形の実行時間が得られることに注意してください。

3 ページ目も同様です。

これにより、整数エッジ重みの線形実行時間と、比較ベースの並べ替えの O(m log n) が得られます。

そして8ページ目：

特に、高速整数ソートを使用すると、おそらく GPA が大幅に高速化されます。

これは、整数値の特別な状況下で O(n) ソート アルゴリズムがあることを意味しますか? それともグラフ理論の専門ですか？

PS:
最初のページで次のように述べているため、参考文献 [3] が役立つ可能性があります。

[..] 整数エッジ重み [3]、[...] などの [..] グラフ クラスのさらなる改善

しかし、どの科学雑誌にもアクセスできませんでした。

4

6 に答える 6

89

はい、基数ソートとカウンティングソートはO(N). Ω(N log N)これらは、下限があることが証明されている比較ベースの並べ替えではありません。

正確には、Radix Sort はO(kN)で、kはソートする値の桁数です。Counting Sort isO(N + k)で、kはソートする数値の範囲です。

k基数ソートとカウンティングソートの両方が実際に線形時間のパフォーマンスを示すほど十分に小さい特定のアプリケーションがあります。

于 2010-02-28T19:30:50.013 に答える
17

比較ソートは、平均で少なくとも Ω(n log n) でなければなりません。

ただし、カウントソートと基数ソートは入力サイズに比例してスケーリングします。これらは比較ソートではないため、入力の固定構造を利用します。

于 2010-02-28T19:32:14.643 に答える
6

カウント ソート: http://en.wikipedia.org/wiki/Counting_sort (整数がかなり小さい場合)。より大きな数がある場合の基数ソート (これは基本的にカウント ソートの一般化、または必要に応じてより大きな数の最適化です): http://en.wikipedia.org/wiki/Radix_sort

バケット ソートもあります: http://en.wikipedia.org/wiki/Bucket_sort

于 2010-02-28T19:34:16.540 に答える
2

あまり実用的ではありませんが (主にメモリのオーバーヘッドが大きいため)、もう 1 つの興味深い線形時間ソート アルゴリズムとしてAbacus (Bead) Sortについて言及したいと思います。

于 2010-03-01T16:00:25.610 に答える