回归n log(n)排序

Question

我有一个排序算法，需要执行n log n排序n次，每一步n递减1 ?换句话说:我期待O(n log n + (n-1) log (n-1) + (n-2) log (n - 2) + ... )的表现。这个问题对我来说肯定不是以前没有遇到过的，所以我必须问:

当n每一步减1时，n log n排序n次的性能的数量级是多少?

Answer 1

N^2 log(N)

你做了N次NlogN操作，所以N次NlogN是解。

哦，经过你的编辑，它完全不同了。这个求和很难求出来但它的上界(都是大0)仍然是N^2 log(N)你也许能找出一个更接近的上限，但我认为这将是一个可行的解决方案。

参见https://math.stackexchange.com/questions/135787/asymptotic-formula-for-the-logarithm-of-the-hyperfactorial获得更精确的解。

更精确的解仍然以N^2 logN为上界(多一点)所以我认为它仍然是一个安全的上界

Answer 2

Time = SUM { k log k } for k: 1..n = log(H(n)) ~ Θ(log(H(n)))

H(n): n中的超阶乘函数

渐近逼近:

我将尝试推导出f(n)作为上界的近似，通过推广k ..

f(n) = log n * SUM { k } for k: 1..n
f(n) = log n * 1/2 n (n+1)
f(n) = 1/2 n log n (n+1)
O(f(n)) = O(1/2 n^2 log n (n+1))
~ O(n^2 log n)

我将尝试推导出g(n)作为下界的近似值，通过推广log(k) ..

g(n) = n * SUM { log(k) } for k: 1..n
g(n) = n * log(1/2 n(n+1))
g(n) = n * (log(1/2) + log(n) + log(n+1))
g(n) = n * (c + log(n) + log(n+1))
g(n) = n * (c + log(n(n+1)))
Ω(g(n)) = Ω(n * (c + log(n^2+n))) = Ω(n * log(n^2+n))
~ Ω(n log(n^2+n))

我们有:

Ω(n log(n^2+n)) < Θ(log(H(n))) < O(n^2 log n)

的例子:

n = 100; Ω(922.02) < Θ(20,756.7) < O(46,051.7)
n = 1000; Ω(1.38 × 10^4) < Θ(3.2 × 10^6) < O(6.9 × 10^6)

注意: f(n)和g(n)是界的渐近逼近，它们是不准确的。

Answer 3

大约0.5 * n <一口> 2> P_6输出(ideone):

1 0 0
2 2 2
3 8 8
4 16 16
5 31 30
6 49 47
7 70 69
8 94 96
9 130 129
10 170 167
...
90 25871 26293
91 26508 26946
92 27152 27608
93 27803 28279
94 28461 28959
95 29126 29647
96 29798 30344
97 30477 31050
98 31163 31764
99 31856 32488
100 32556 33220

Answer 4

是Theta(N^2 log N)。

显然是O(N^2 log N)。

为了显示它是Omega(N^2 log N)，只考虑序列的大一半，其中k的每个值至少是N/2。为简单起见，假设N是偶数。

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)