11

アルゴリズムのコースを受講していますが、ソートをカウントする時間計算量はO（n + k）であることがわかりました。ここで、kは数値の範囲、nは入力サイズです。私の質問は、k = O（n 2）またはO（n 3 ）のように、kとnの差が大きすぎる場合、複雑さはO（n 2）またはO（n 3）であると言えます。？この場合、ソートをカウントすることは賢明なアプローチではなく、マージソートを使用できます。私は正しいですか？

4

2 に答える 2

10

はい、あなたはすべての点で正確に正しいです。

さらに、より強力なステートメントを作成できます。k= O（n 2）またはO（n 3 ）の場合、カウントソートの複雑さはΘ（ n2）またはΘ（n3）であると言えます。

于 2013-03-24T14:24:19.153 に答える
3

理論的には、O（n）時間でソートできます。値の範囲が1〜n 3の場合は、基数nに変換し、基数ソートを実行します。基数nでは、数値は3桁であるため、基数変換の実行時間はO（3n + 3n）+ O（n）です。全体的なO（n）。

于 2013-07-09T10:04:24.037 に答える