algorithm - f(n) = Sigma of I*Log(I) ，其中 I=1 到 Log(n) ，等于什么？

Question

我正在尝试计算以下内容:

f(n) = ∑ (i*log(i))  , when i=1 to log(n) . 

我该怎么做？

我已经成功了:

f(n) = ∑ (i*log(i))  , when i=1 to n . 

这是:1*log(1) + 2*log(2) + ... + n*log(n) <= n(n*log(n))

到底在哪里:f(n) = ∑ (i*log(i)) = Ω(n^2 log^2(n) ) ( Where i=1 to n )

但是我不知道第一个怎么做，有人知道吗？

问候

Answer 1

首先，您必须从 log^2(n) 中删除 ^2，您当前的结果将是

f(n) = ∑ (i*log(i)) <= n(n*log(n)) = Ω(n^2*log(n))

然后，对于 i 从 1 到 log(n) 的情况，只需替换 n通过 log(n)。

让我们定义

g(n) = ∑ (i*log(i)), when i=1 to log(n) // The result you are looking for
f(n) = ∑ (i*log(i)), when i=1 to n // The result we have

然后

g(n) = f(log(n)) = Ω(log(n)^2*log(log(n)))