すべての質問
2 件の質問
6
票
1
回答
843
閲覧数
量子コンピュータによってソートは速くなりますか?
ランダムアクセスできる配列に対してソートを行うとき、量子アルゴリズムは逐次の古典的アルゴリズムより漸近的に速くなりえますか?
1
票
1
回答
683
閲覧数
ソートに必要な最低計算量は n log n ではないのか?
長さ n の配列をソートするには、最低でもオーダーで n log n の時間計算量が必要だと聞きました。しかし Wikipedia のソートの記事を見ると、バケットソートやバイトニックソートの平均時間計算量は n log n を下回っているように見えます。何故でしょうか?