長さ n の配列をソートするには、最低でもオーダーで n log n の時間計算量が必要だと聞きました。しかし Wikipedia のソートの記事を見ると、バケットソートやバイトニックソートの平均時間計算量は n log n を下回っているように見えます。何故でしょうか?
-
上記wikiの記事に[要出典]を書いて文献が明らかになるようにしておきました。– Haruo WakakusaCommented 2019年1月23日 12:01
-
時間計算量は「最悪の時間計算量」にして下さい– Haruo WakakusaCommented 2019年1月23日 12:02
-
1@ポジティブうざいリグルちゃん さん、日本語版 Wikipedia に書かれているのは最悪時間計算量が Ω(n log n) である証明ですが、実は平均時間計算量も Ω(n log n) なので問題ありません。たとえば英語版 Wikipedia の "Comparison sort" をご覧ください。– nekketsuuu ♦Commented 2019年1月23日 13:01
コメントを追加
|
1 件の回答
バケットソートやバイトニックソートが逐次の「比較ソート」ではないからです。
比較ソートとは、大雑把に言うと、ランダムアクセスによる読み書きができる配列に対して、操作として要素の比較と読み書きのみが許されている状況下でのソートアルゴリズムのことです。そしてこの比較ソートを逐次に行う場合の平均時間計算量が Ω(n log n) になります。
それ以外の場合、Ω(n log n) を下回ることがあります。バケットソートは配列の要素の種類が分かっていることが前提にあるため、比較ソートではありません。バイトニックソートは並列計算を使ったアルゴリズムであり、逐次のアルゴリズムではありません。