Вопрос о асимптотическом анализе: sum [log (i) * i^3, {i, n}] является большой тетой (log (n) * n^4)

Question

У меня вопрос о домашнем задании, который меня озадачил. Он просит, чтобы вы доказали, что функция Sum [log (i) * i^3, {i, n}) (т. Е. Сумма log (i) * i^3 от i = 1 до n) является big-theta (журнал (п) * п^4).

Я знаю, что Sum [i^3, {i, n}] является ((n (n + 1))/2)^2 и что Sum [log (i), {i, n}) является log (n!), но я не уверен, что 1) я могу рассматривать эти два отдельно, поскольку они являются частью одного и того же продукта внутри суммы, и 2) как начать получать это в форму, которая поможет мне с доказательство.

Любая помощь была бы действительно оценена. Благодаря!

Answer 1

серии выглядит следующим образом - журнал 1 + 2 * войти 2^3 + 3 * войти 3^3 .... (до n условий) сумма которых не сходится. Так что, если мы интегрируем его

Интеграл (1 до бесконечности) [LogN * п^3] (интегрирование по частям)

вы получите 1/4 * LogN * п^4 - 1/16 * (п^4)

Очевидно, что доминирующая термин есть LogN * п^4, поэтому он принадлежит к Большому Theta (журнал N * N^4)

другой путь вы могли бы смотреть на это -

Серия выглядит как log 1 + log2 * 8 + log 3 * 27 ...... + log n * n^3. Вы можете думать о log n как о термине с наивысшим значением, так как все логарифмические функции растут с одинаковой скоростью асимптотически,

Вы можете рассматривать приведенные выше серии как log n (1 + 2^3 + 3^3. ..), который является

журнал п [п^2 (п + 1)^2]/4

Предполагая, что F (п) = п * войти п^4 г (п) = N [войти n^2 (n + 1)^2]/4

Вы можете показать, что lim (n стремится к inf) для f (n)/g (n) будет константой [с применением правила L'Hopital]

Это еще один способ доказать, что функция g (n) принадлежит Большой тете (f (n)).

Надеюсь, что это поможет.

Answer 2

Подсказка для одной части вашего решения: насколько велика сумма последних двух слагаемых вашей левой суммы?

Подсказка для второй части: если вы разделите левую часть (сумму) на правую сторону, сколько сгенерированных вами сумм? Насколько велика самая большая?

Подсказка для первой части снова: найдите простую оценку снизу для суммы от n/2 до n в вашем первом выражении.

Answer 3

Исследуйте определение и использование определения BigO.

Для исчисления вы можете использовать некоторую компьютерную алгебраическую систему.

В следующем ответ, я показал, как сделать это с помощью Maxima Opensource CAS: Asymptotic Complexity of Logarithms and Powers