log (n!) эквивалентно nlogn?(Обозначение Big O) - PullRequest
Новая
       16

log (n!) эквивалентно nlogn?(Обозначение Big O)

0 голосов
/ 26 сентября 2018

В моей книге есть вопрос с несколькими вариантами ответов:

Что такое большая буква O для следующей функции: n ^ log (2) + log (n ^ n) + nlog (n!)

Я знаю, что log (n!) Принадлежит O (nlogn), но я читал в Интернете, что они эквивалентны.как log (n!) - это то же самое, что сказать nlogn?как это: log (n!) = logn + log (n-1) + ... + log2 + log1 эквивалентно nlogn?

1 Ответ

0 голосов
/ 26 сентября 2018

Пусть n/2 будет частным от целочисленного деления n на 2.У нас есть: 

log(n!) =  log(n) + log(n-1) + ... + log(n/2) + log(n/2 - 1) + ... + log(2) + log(1)
        >= log(n/2) + log(n/2) + ... + log(n/2) + log(n/2 - 1) + ... + log(2)
        >= (n/2)log(n/2) + (n/2)log(2)
        >= (n/2)(log(n) -log(2) + log(2))
        =  (n/2)log(n)

, затем 

n log(n) <= 2log(n!) = O(log(n!))

и n log(n) = O(log(n!)).И наоборот, 

log(n!) <= log(n^n) = n log(n)

и log(n!) = O(n log(n)).

...