6

アルゴリズム第2版の紹介を読んでいますが、線形時間で0からn3-1までのn個の整数をソートできるという質問があります。私はIBMの基数ソートアプローチを考えています。最下位桁から始めて、最下位桁に関して数字を分離し、次にソートしてから、次の最下位桁に関して分離します。各分離にはO（n）時間がかかります。しかし、疑問があります。たとえば、数値の1つがn桁で構成されている場合、アルゴリズムにはO（1 * n + 2 * n + ... + n * n）= O（n 2）時間がかかります。数字がn桁未満であることを保証できますか、それとも誰かが質問に対して別のヒントを与えることができますか？ありがとう

4

2 に答える 2

3

基数ソートの複雑さは、数値の桁数O(dn)と同じです。d

dが一定の場合にのみ、アルゴリズムは線形時間で実行されます。あなたの場合d = 3log(n)、アルゴリズムは で実行されO(nlog(n))ます。

正直なところ、この問題を線形時間で解決する方法がわかりません。数字の性質に関する他の情報はありますか? 数字の性質について欠落している他の情報があるかどうか疑問に思っています...

于 2013-03-10T19:14:18.857 に答える
2

ワード RAM モデルを想定し、n が O(1) ワードに収まると仮定すると、線形時間アルゴリズムが存在します。

すべての数値を基数 n で書き込み、基数ソートを実行します (基礎となる桁ソートとしてカウントソートの安定バージョンを使用)。

無制限の n を想定したい場合、入力のサイズは実際には n log n になります。この場合、基数ソートは再び (O(n log n) 時間で) 機能し、技術的に言えば、それでも線形時間アルゴリズムです! （もちろん、これはまだ算術がO（1）であると仮定していると思います...）

于 2013-03-11T03:08:13.800 に答える