10
私はアルゴリズムのコースを取っており、ソートを計算する時間の複雑さがO（n + k）であることがわかりました。ここで、kは数値の範囲、nは入力サイズです。私の質問は、k = 0（n ）やO（n ）のように、kとnの差が大きすぎる場合、複雑さはO（n ）またはO（n ）？この場合、ソートのカウントは賢明な方法ではなく、マージソートを使用できます。私は正しい？ソートを計算する時間の複雑さ
A
答えて
7
はい、正確にすべてのカウントに当てはまります。
さらに、我々は強力なステートメントを作ることができる：K = O（N ）またはO（N ）は、我々は、計数ソートの複雑さは、Θ（N ）以上であると言うことができる場合Θ（n ）。
3
理論的にはO（n）時間でソートすることはできます。値の範囲が1からn の場合、基数nに変換し、基数ソートを行います。ベースnには3桁の数字があるので、実行時間はベース変換のO（3n + 3n）+ O（n）です。全体的なO（n）。
+0
あなたはベースのn個の数字に対して 'O（1）'演算を行っていると仮定しています。一般的には成立しそうにないようです。 – jfs
答えをいただきありがとうございます。私はちょうど私が正しく理解しているかどうかを確認したかっただけです。 –