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