3

我有一个排序算法需要执行n log n排序n时间，每一步 n 减 1？换句话说：我期望的表现是O(n log n + (n-1) log (n-1) + (n-2) log (n - 2) + ... ). 这个问题绝对不会让我觉得以前没有遇到过，所以我必须问：

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

4

4 回答 4

2

N^2 对数(N)

您正在执行 NlogN 操作 N 次，因此 N 次 NlogN 是解决方案。

哦，经过您的编辑，情况完全不同。很难算出总和，但它的上限（所有大 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 回答
1

大约是 0.5 * n 2 * log(n)：

#include <stdio.h>
#include <math.h>

#define MAX 100
double sum[1 + MAX];

int main(void)
{
  int i;

  sum[0] = 0;

  for (i = 1; i <= MAX; i++)
  {
    sum[i] = sum[i - 1] + i * ceil(log2(i));
    printf("%i %.0f %.0f\n", i, sum[i], ceil(log2(i) * i * i / 2));
  }

  return 0;
}

输出（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
于 2013-04-03T03:44:59.660 回答
1 
Time = SUM { k log k } for k: 1..n = log(H(n)) ~ Θ(log(H(n)))

H(n)：n 中的超因子函数

渐近近似：

我将尝试通过推广 k 来推断 f(n) 作为上限的近似值。

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)

我将尝试通过推广 log(k) 来推断 g(n) 作为下限的近似值。

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) 是边界的渐近近似，它们不准确..

于 2013-04-03T20:43:58.717 回答
0

是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)
于 2013-04-03T18:55:21.907 回答