Welke functie groeit sneller, exponentieel (zoals 2^n, n^n, e^n enz.) of faculteit (n!)?
Ps: ik las net ergens, n! groeit sneller dan 2^n.
Antwoord 1, autoriteit 100%
n! groeit uiteindelijk sneller dan een exponentiële met een constante basis (2^n en e^n), maar n^n groeit sneller dan n! omdat de basis groeit naarmate n toeneemt.
Antwoord 2, autoriteit 69%
n! = n * (n-1) * (n-2) * ...
n^n = n * n * n * ...
Elke term na de eerste in n^nis groter, dus n^n zal sneller groeien.
Antwoord 3, autoriteit 3%
n^nwordt groter dan n!— voor een uitstekende uitleg, zie het antwoord van @AlexQueue.
Voor de andere gevallen, lees verder:
Factoriële functies worden asymptotisch groter dan exponentiële functies, maar het is niet meteen duidelijk wanneer het verschil begint. Voor n=5en k=10is de faculteit 5!=120bijvoorbeeld nog steeds kleiner dan 10^5=10000. Om erachter te komen wanneer faculteitsfuncties groter worden, moeten we een snelle wiskundige analyse uitvoeren.
We gebruiken de formule van Stirling en eenvoudige logaritmemanipulatie:
log_k(n!) ~ n*log_k(n) - n*log_k(e)
k^n = n!
log_k(k^n) = log_k(n!)
n*log_k(k) = log_k(n!)
n = log_k(n!)
n ~ n*log_k(n) - n*log_k(e)
1 ~ log_k(n) - log_k(e)
log_k(n) - log_k(e) - 1 ~ 0
log_k(n) - log_k(e) - log_k(k) ~ 0
log_k(n/(e*k)) ~ 0
n/(e*k) ~ 1
n ~ e*k
Zodra nbijna 3 keer zo groot is als k, zullen faculteitsfuncties groter worden dan exponentiële functies. Voor de meeste real-world scenario’s zullen we grote waarden van nen kleine waarden van kgebruiken, dus in de praktijk kunnen we aannemen dat faculteitsfuncties strikt groter zijn dan exponentieel functies.
Antwoord 4, autoriteit 2%
Ik wil je een meer grafische methode laten zien om dit heel gemakkelijk te bewijzen. We gaan delen gebruiken om een grafiek van een functie te tekenen, en het zal ons dit heel gemakkelijk laten zien.
Laten we een eenvoudige en saaie delingsfunctie gebruiken om een eigenschap van deling uit te leggen.
Als a toeneemt, neemt ook de evaluatie van die uitdrukking toe. Als b afneemt, neemt ook de evaluatie van die uitdrukking af.
Met dit idee kunnen we een grafiek plotten op basis van wat we verwachten te stijgen en te verminderen, en een vergelijking maken welke sneller toeneemt.
In ons geval willen we weten of exponentiële functies sneller groeien dan faculteiten, of omgekeerd. We hebben twee gevallen, een constante naar een variabele exponent versus een variabele faculteit, en een variabele naar een variabele exponent versus een variabele faculteit.
Als we deze tools in kaart brengen met Desmos (geen affiliatie, het is gewoon een leuke tool), zien we dit:
Grafiek van een constante naar variabele exponent, vs variabele faculteit
Hoewel het aanvankelijk lijkt dat de exponentiële uitdrukking sneller toeneemt, bereikt het een punt waarop het niet langer zo snel toeneemt, en in plaats daarvan neemt de factoriële uitdrukking sneller toe.
Grafiek van een variabele naar variabele exponent, vs variabele faculteit
Hoewel het aanvankelijk langzamer lijkt te zijn, begint het snel voorbij dat punt te stijgen, daarom kunnen we concluderen dat de exponentiële sneller moet toenemen dan de faculteit.