私はアルゴリズム第2版の紹介を読んでおり、0からnまでの整数nを並べ替えることができるとの質問があります。 -1私はIBMの基数ソート手法を考えています。私は、最下位桁から始まり、最下位桁に関して別々の数字を並べ替え、次にソートして次の最下位桁などについて分離します。各分離にはO（n）時間がかかります。しかし、例えば数字の1つがn桁で構成されている場合、アルゴリズムはO（1 * n + 2 * n + ... + n * n）= O（n ）右？数字がn桁未満であることを保証することはできますか、誰かが質問のヒントを与えることはできますか？ありがとう線形時間で並べ替える
基数ソートの複雑さは、数字の桁数としてO(dn)とdです。
アルゴリズムは、dが一定の場合にのみ線形時間で実行されます。あなたのケースではd = 3log(n)であり、アルゴリズムはO(nlog(n))で実行されます。
正直なところ、この問題を線形時間に解決する方法がわかりません。数字の性質に関する他の情報がありますか？数字の性質について他の情報が欠落しているのではないかと疑問に思っています...
答えに感謝、私は実際に答えを見つけた、基数nの桁の数字を2桁の数字にソートします。合計時間はO（n）です – yrazlik
2桁の「キー」で数字を壊した場合、「d = 3log（n）/ 2」になりませんか？あなたはアルゴリズムの詳細な分析へのリンクを持っていますか？ありがとうございます – Gevorg
実際には、私は本のインストラクターのマニュアルからそれを見つけました。ここには正確に言われています： 数字を基数nで2桁の数字として扱います。各桁の範囲は0〜n -1です。 これらの2桁の数字を基数ソート順に並べ替えます。 合計の時間がΘ（n）であるように、それぞれΘ（n + n）=Θ（n）時間を取る2回のカウントソートがあります。 – yrazlik
nがRAMモデルであり、nがO （1）単語、線形時間アルゴリズムがあります。
すべての数値を基数nで書き込み、基数ソートを行います（基本的なソートとして安定したカウントソートを使用します）。
無制限のnを仮定したい場合は、入力のサイズを実際にn log nとします。この場合、基数ソートが再び働きます（O（n log n）時間内）、技術的に言えば、線形時間アルゴリズム！ （もちろん、これはまだ算術がO（1）であると仮定します）
実際に 'linear'は' linear'ですか？ – Gevorg
私たちはしばらく話していたので、フォローアップするだけです！ :)あなたは 'O（nlog（n））'にどうなっているのか分かりませんが、これを線形解法として受け入れると、問題はQuickSort、MergeSortなどの優れた実装で簡単に解けます。 – Gevorg
@Gevorg：いいえ、整数をO（log n）、クイックソートなどをTheta（n（log n）^ 2）と比較します。基礎となる計算モデルは重要です。ほとんどのアルゴリズムの教科書は、WORD RAMモデルを使用しています（実際には、実際のコンピュータに最も近いため、ほとんどの人がそれを考えずに使用しています）。この場合、WORD RAMモデルでは、入力サイズはTheta（n）、基数ソートはO（n）、クイックソートなどはO（n log n）です。 – Knoothe
各数値は0〜n^3 - 1です。したがって、最大3桁の基数nを持ちます。 –
この情報で、私のソリューションは正しく動作します。 – yrazlik
はい私はそう信じています。 –