Что такое BIG- $ O $ ORECTION о суммировании журнала?

Question

для: $$ \ sum ^ {n + m} _ {i= n} \ log (i) $$ Мне интересно, что такое большая нотация и как это доказать ... Я считаю, что мы также можем написать это как $$ \ log (n) + \ log (n + 1) + \ log (n + 2) + \ ldots + \ log (n + m) $$

также $$ \ log (n + m)! / \ log (n - 1)! $$

Спасибо

Answer 1

Напомним, что сумма $ \ log $ используется эквивалентна $ \ log $ изделий.

Это:

$$ \ log (xy)=log x + \ log y $$

Таким образом, мы можем изменить вашу функцию:

$$ \ begin {align} \ sum_ {i= n} ^ {n + m} \ log I &=log \ prod_ {i= n} ^ {n + m} i \\ &=log (n \ cdot (n + 1) \ cdot (n + 2) \ cdot \ ldots \ cdot (m - 1) \ cdot m) \\ &=log (m! \ / \ (n - 1)!) \\ \ end {align} $$

Тогда мы можем аналогично использовать правило разделения, чтобы получить их обратно:

$$ \ log (m! \ / \ (n-1)!)=log (m!) - \ log ((n - 1)!) $$

Тогда с помощью Стерлинг-аппроксимация Мы можем сразу увидеть:

$$ \ log (m!) - \ log ((n - 1)!)= o (m \ log m) $$

Вы можете сделать лучше, хотя, взяв более точные оценки, чтобы получить:

$$ \ begin {align} \ log (m!) - \ log ((n-1)!) & \ leq em ^ {m + \ frac {1} {2}} e ^ {- m} - \ sqrt {2 \ pi} (n -1) ^ {n- \ frac {1} {2}} e ^ {1-n} \\ &=vdots \ end {align} $$

Answer 2

o ((m +1) log (n + m)).Это, очевидно, верхняя граница.Но также большинство значений имеют логарифм близко к максимуму, так что это также хорошая нижняя граница.

В вашем особо простой случае формула Stirling даст вам лучший результат, но вы просили только для Big-O.