このウェブページで私は読むことができます：
いくつかの特殊なケースのアルゴリズム (1 つの例は、プログラミング パールで説明されています) は、特定のデータ セットを O(n*log(n)) よりも高速に並べ替えることができます。これらのアルゴリズムは、並べ替えられるアイテムの比較に基づいておらず、トリックに依存しています。O(n*log(n)) よりも優れたパフォーマンスを発揮する鍵比較アルゴリズムはないことが示されています。
非比較アルゴリズムというのは初めて聞きました。誰かがそれらのアルゴリズムの 1 つの例を教えてくれ、O(nlog(n)) よりも速く並べ替えの問題を解決する方法をよりよく説明できますか? そのウェブページの作成者が話しているのは、どのようなトリックですか?
論文やその他の優れた情報源へのリンクは大歓迎です。ありがとうございました。
まず、用語をまっすぐにしましょう。
O(n logn)。O(n logn)。バケットソートはそのような例の1つです。2番目のクラスの直感的な例を示すために、入力配列が完全に0と1で構成されていることを知っているとします。ゼロと1の数を数えて、配列を反復処理できます。n0最終カウントとを呼び出しましょうn1。次に、出力配列を反復処理し、n00の後に1を書き込みn1ます。これはO(n)並べ替えアルゴリズムです。
データの特殊な構造を利用することによってのみ、この問題の線形時間アルゴリズムを思い付くことができました。これは、汎用の主要な比較アルゴリズムとは対照的です。このようなアルゴリズムは、1つのことを除いて、データについて何も知る必要はありません。2つの要素のソートキーを比較する方法を知る必要があります。言い換えると、任意の2つの要素が与えられた場合、ソートされた配列の最初に来る必要がある要素を知る必要があります。
たった1つのアルゴリズムを使用して想像できるあらゆる方法で何でもソートできることの代償は、そのようなアルゴリズムがO(n logn)平均よりもうまくいくことを期待できないということです。