Domanda sugli alberi -Algoritmi e strutture dati

[dungedra]

Buongiorno a tutti, ho da poco iniziato a studiare algoritmi e strutture dati,
sono arrivato a leggere qualcosa sugli alberi di decisione, tutte le varie soluzioni sul numero di foglie e sul numero di nodi totali (che dovrebbero valere per gli alberi equilibriati)....

ora però mi sono imbattuto in una parte in cui c' è scritto questo:

$ n_{foglie} =n! $

$ n! \sim \sqrt{2 \pi n} ( n/e )^{n} ( 1+ \Theta(1/n) ) $

$ n! > (n/e)^{n} $

$ \log( n! ) > \Theta(n \log n) $

mi potreste spiegare come si giunge a ciascuno di questi passaggi e se queste pseudo-regole, valgono solo per gli alberi non equilibriati::::

spero in una vostra risposta, grazie comunque...

[apatriarca]

Ti ho corretto un po' le formule che erano poco leggibili.

I passaggi che hai scritto utilizzano l'approssimazione di Stirling.

[hamming_burst]

"toto1991":
$ \log( n! ) > \Theta(n \log n) $

non può essere $\Theta$. Al massimo limitazione inferiore: $ \log( n! ) > \Omega(n \log n)$ o se c'è minore stretto $\omega()$, ma non inclusa anche una limitazione superiore.