Доказательство Big-O с использованием суммы журналов

Здесь могут помочь два полезных математических факта. Во-первых, обратите внимание, что x x + 1 для любого x. Поэтому,

сумма от i = 1 до n (log (n/i)) (сумма от i = 1 до n log (n / i)) + n

Поэтому, если мы сможем показать, что вторая сумма равна O(n), мы закончим.

Используя свойства журналов, мы можем переписать

лог(n/1) + лог(n/2) + ... + лог(n/n)

= лог(nⁿ / n!)

Давайте посмотрим, сможем ли мы упростить это. Используя свойства логарифмов, получаем, что

log(nⁿ / n!) = log(nⁿ) - log(n!)

= n log n - log (n!)

Теперь мы можем использовать приближение Стирлинга, которое говорит, что

журнал (n!) = n журнал n - n + O (log n)

Поэтому:

n log n - лог (n!)

= n log n - n log n + n - O (log n)

= O(n)

Таким образом, сумма равна O(n), как и требовалось.

Надеюсь это поможет!

Как правило, мы знаем, что:

Следовательно: