Skip to main content

すべての質問

でタグ付けされた
絞り込み
並べ替え
タグ付けされた
6
1 回答
843 閲覧数

量子コンピュータによってソートは速くなりますか?

ランダムアクセスできる配列に対してソートを行うとき、量子アルゴリズムは逐次の古典的アルゴリズムより漸近的に速くなりえますか?
nekketsuuu's user avatar
  • 2.4万
1
1 回答
683 閲覧数

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

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