Какова производительность журнала (n!) По сравнению с n?

Question

Мне было интересно, является ли log (n!) O (n) или n - O (log (n!)). Я видел, что log (n!) - это O (n log (n)), но нет никакой информации, которую я могу найти доступной для моего конкретного вопроса.

Answer 1

Приближение Стерлинга подразумевает, что log(n!) = Θ(n log(n)). В частности, это не правда, что log(n!) = O(n), и это правда, что n = O(log(n!)).

Answer 2

Log (n!) Растет намного быстрее по сравнению с n. Вы можете видеть на картинке. Пример: Когда n = 50, O (n) будет 50. Но O (log (n!)) = 64,48.

Обновление :

Я попытался построить n и log (n!) На том же графике.

log(n!) = O(n) for 0 < n < 25 
n = O(log(n!)) for n > 25