Сложность $ O (\ log (n ^ n)) $ vs $ o (\ log (n!)) $

Question

- $ O (\ log (n ^ n)) ?Есть ли хороший / практический алгоритм с таким сложностью?

А также, чтобы проверить мое понимание алгоритмической сложности, эти два $> O (n \ log (n)) $ ?

Я только начинаю с этой темы и не совсем уверен, если я получаю это правильно.

Спасибо и оставаться в безопасности.

Answer 1

$ o (\ log n ^ n) $ и $ O (\ log n!) $ Оба описывают тот же набор функций.

Обратите внимание, что $ (\ frac {n} {e}) ^ n \ le n!\ le n ^ n $ и, следовательно:

$ o (n \ log n)= o (n \ log \ frac {n} {e})= o (\ log (\ frac {n} {e}) ^ n) \ subsEtq o (\ log n!) \ subsEtq o (\ log n ^ n)= o (n \ log n) $ .

Это показывает, что все вышеперечисленные наборы совпадают.

Answer 2

$ n ^ n $ намного больше, чем n!. Первые умножения n x x n x n x ... x n (n раз), последние умножает 1 x 2 x 3 x 4 x ... x n. Так что это очевидно , что $ o (\ log (n ^ n)) не правда. $ o (\ log (n ^ n))> o (\ log (n!)) $ менее очевиден, но и не правда.

Это потому, что мы принимаем логарифм с обеих сторон. Принимая логарифмы меняет продукты на суммы и показатели продуктам (очень примерно). И если мы возьмем продукт для n!, Очевидно, что у нас есть факторы N / 2 больше, чем N / 2, так что n! > $ (n / 2) ^ {n / 2} $ . Принимая логарифм, войдите! > (N / 2) Журнал (N / 2). Для N> 4 у нас есть N / 2> $ n ^ {1/2} $ , следовательно, журнал N / 2> (log n) / 2, поэтому журнал N ! > (N / 2) Журнал (N / 2)> N / 4 LOG N= 1/4 Журнал $ N ^ n $ .

Так журнал!= $ \ theta (\ log n ^ n) $ .