3

各ステップで n が 1 ずつ減少する、n log n並べ替え回数を実行する必要がある並べ替えアルゴリズムがありますか? n言い換えれば、私は のパフォーマンスを期待しますO(n log n + (n-1) log (n-1) + (n-2) log (n - 2) + ... )。この問題は、以前に遭遇したことのないものとして私を襲うことは絶対にないので、質問する必要があります:

各ステップで n が 1 ずつ減少する場合のn log nソート時間の桁違いのパフォーマンスは?n

4

4 に答える 4

2

N^2 log(N)

NlogN 操作を N 回実行しているため、NlogN の N 回が解決策です。

ああ、あなたの編集後、それはかなり異なります。その合計を把握するのは非常に困難ですが、上限 (これはすべて大きな O です) は依然として N^2 log(N) です。より近い上限を見つけられるかもしれませんが、それが実行可能な解決策になると思います。

より正確な解については、https://math.stackexchange.com/questions/135787/asymptotic-formula-for-the-logarithm-of-the-hyperfactorialを参照してください。

はるかに正確な解は、依然として N^2 logN (かなり) で制限されているため、それでも安全な上限であると思います。

于 2013-04-03T03:29:24.623 に答える
0

ですTheta(N^2 log N)。

それは明らかにO(N^2 log N)です。

それが であることを示すために、 の各値が少なくともOmega(N^2 log N)であるシーケンスの大半分だけを考えてください。簡単にするために、は偶数であると仮定します。kN/2N

Sum[k=1..N](k log k) >= Sum[k=N/2..N](k log k)           ; drop the small half
                     >= Sum[k=N/2..N]((N/2) log (N/2))   ; since each k >= N/2
                     >= N/2 * N/2 * log (N/2)
                      = N^2/4 * (log N - log 2)
                      = N^2/4 * logN - c
                      ∈ Omega(N^2 log N)
于 2013-04-03T18:55:21.907 に答える