10

重複の可能性：
長さNの配列には、値1、2、3…N^2を含めることができます。O（n）時間でソートすることは可能ですか？

n範囲内の数値が与えられた場合、 O（n）実行時[0,n^2 -1]にそれらをどのようにソートできますか？

解決策が含まれているような気がしますがradix sort、まだ何かが足りません。

数値はn整数です。

何か案は ？

備考：宿題ではありません！

よろしく

4

2 に答える 2

3

運が悪いと思います。基数ソートはO（k * n）です。ここで、kは桁数です。あなたの場合、k = log（n ^ 2）であり、結果はO（n * log（n））になります。

于 2012-08-20T17:27:57.893 に答える
3

実際の時間はあなたが持っているデータの分布に依存しますが、私は次のことをします：

  • n個のバケットを作成します。
  • 各数値を調べて、値iの要素をバケットsqrt（i）に入れます。
  • 各バケットを調べて、バケット内の各要素に対して基数ソートを実行します。
于 2012-08-20T17:38:17.010 に答える