Complessità di $ o (\ log (n ^ n)) $ vs $ o (\ log (n!)) $

Question

$ o (\ log (n ^ n)) ?C'è un algoritmo buono / pratico con questo tipo di complessità?

E anche, per controllare la mia comprensione della complessità algoritmica, sono queste due $> o (n \ log (n)) $ ?

Sto appena iniziando con questo argomento e non proprio sicuro se lo sto ottenendo bene.

Grazie e stare al sicuro.

Answer 1

$ o (\ log n ^ n) $ e $ o (\ log n!) $ Entrambi descrivono lo stesso set di funzioni.

Si noti che $ (\ frac {n} {e}) ^ n \ le n!\ le n ^ n $ e quindi:

$ o (n \ log n)= o (n \ log \ frac {n} {e})= o (\ log (\ frac {n} {e}) ^ n) \ SOTETEQ o (\ log n!) \ SOTETETQ O (\ log n ^ n)= o (n \ log n) $ .

Questo dimostra che tutti i set sopra riportati coincidono.

Answer 2

$ n ^ n $ è molto più grande di n!. La prima moltiplica n x x n x n x ... x n (n volte), quest'ultimo moltiplica 1 x 2 x 3 x 4 x ... x n. È ovvio che $ o (\ log (n ^ n)) non lo è vero. $ o (\ log (n ^ n))> o (\ log (n!)) $ è meno ovvio, ma anche non vero.

Questo perché stiamo prendendo il logaritmo su entrambi i lati. Assunzione di logaritmi modifica i prodotti per somme ed esponenti ai prodotti (molto approssimativamente). E se prendiamo il prodotto per n!, È ovvio che abbiamo n / 2 fattori superiori a n / 2, quindi n! > $ (n / 2) ^ {n / 2} $ . Prendendo il logaritmo, log n! > (N / 2) Log (N / 2). Per n> 4 Abbiamo n / 2> $ n ^ {1/2} $ , quindi log n / 2> (log n) / 2, quindi log n) ! > (N / 2) Log (N / 2)> N / 4 log n= 1/4 log $ n ^ n $ .

Quindi il log n!= $ \ theta (\ log n ^ n) $ .