Skip to main content
1 / 2
nekketsuuu
  • 2.4万
  • 12
  • 53
  • 117

ソートに必要な最低計算量は n log n ではないのか?

長さ n の配列をソートするには、最低でもオーダーで n log n の時間計算量が必要だと聞きました。しかし Wikipedia のソートの記事を見ると、バケットソートやバイトニックソートの平均時間計算量は n log n を下回っているように見えます。何故でしょうか?

nekketsuuu
  • 2.4万
  • 12
  • 53
  • 117