f (n) = сигма 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

f (n) = тета (log ² (n) * log (log (n))

Доказательство:

f(n) = 1 * log(1) + 2 * log(2) + ... + log(n) * log(log(n)) <= 
<= log(n)*log(log(n)) * log(n) =
= O(log^2(n) * loglog(n))

f(n) = 1 * log(1) + 2 * log(2) + ... + log(n) * log(log(n)) >= 
>= log(n/2) * log(log(n/2)) + log(n/2 + 1) * log(log(n/2 + 1) + ... + log(n) * log(log(n)) >= 
>= log(n/2) * log(log(n/2)) + ... + log(n/2) * log(log(n/2)) = 
= log(n/2) * log(log(n/2)) * log(n/2)
= log^2(n/2)*log(log(n/2)) = log^2(n/2)*log(log(n)-log(2)) = 
= Omega(log^2(n)*loglog(n))

Answer 2

Если вы знаете какое-то исчисление, вы часто можете найти порядок роста таких сумм путем интегрирования.

Если f является положительной монотонной функцией, ∑ f(i) для 1 <= i <= k может быть аппроксимированоинтеграл ∫ f(t) dt (t в диапазоне от 1 до k).Поэтому, если вам известна примитивная функция F из f (на современном языке антидериватив ), вы можете легко оценить интеграл до F(k) - F(1).Для анализа роста постоянный член F(1) не имеет значения, поэтому вы можете аппроксимировать сумму (а также интеграл) просто на F(k).

Инструмент, который часто полезен в таких вычислениях, - частичная интеграция ,

b                                         b
∫ f'(t)*g(t) dt = f(b)*g(b) - f(a)*g(a) - ∫ f(t)*g'(t) dt
a                                         a

, что следует из правила продукта (f*g)' = f' * g + f * g'.Часто полезно написать f как 1*f, чтобы применить частичную интеграцию, например, чтобы найти примитив (натурального) логарифма,

∫ log t dt = ∫ 1*log t dt = t*log t - ∫ t * (log t)' dt = t*log t - ∫ t*(1/t) dt = t*log t - t

В этом случае с f(t) = t*log tчастичная интеграция дает

∫ t*log t dt = 1/2*t^2 * log t - ∫ (1/2*t^2) * (log t)' dt
             = 1/2*t^2 * log t - 1/2 ∫ t^2*(1/t) dt 
             = 1/2*t^2 * log t - 1/4*t^2

Поскольку второй член растет медленнее, чем первый, его можно игнорировать для анализа роста, поэтому вы получаете

k
∑ i*log i ≈ 1/2*k^2*log k
1

, поскольку логарифмы для разных оснований отличаются толькопо постоянному коэффициенту другой выбор логарифма просто меняет постоянный коэффициент, и вы видите, что во всех случаях

k
∑ i*log i ∈ Θ(k^2 * log k)
1

Для вашей конкретной задачи k = log n, поэтому сумма равна Θ((log n)^2 * log(log n)), так какдругие ответы были получены по-другому.

Answer 3

Во-первых, вы должны удалить ^2 из log^2(n), в результате ваш текущий результат будет

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)))

Answer 4

http://img196.imageshack.us/img196/7012/5f1ff74e3e6e4a72bbd5483.png теперь подставьте n для logn, и вы получите ОЧЕНЬ жестко ограниченный log ^ 2 (n) * log (log (n))