Funktionen sortieren < Funktionen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:59 So 15.02.2009 | | Autor: | alexmart |
| Aufgabe | | Ordnen sie folgende Funktionen in aufsteigender Reihenfolge nach ihrem asymptotischen Wachstum bzgl. der O-Notation und geben sie jeweils eine kurze Begründung an: [mm] 2^{lg n}, 2^{n}, [/mm] n log n, [mm] (\bruch{7}{8})^{n}, n^{k}, [/mm] 1, n! (Fakultät). |
Hi,
ich habe diese Frage nur hier gestellt.
Die O-Notation ist mir bekannt und auch klar, wie ich überprüfe, ob eine Funktion in einer bestimmten Laufzeitklasse ist.
Bei dieser Aufgabe verwirrt mich nur die Konstante k ein bisschen.
Erstmal meine Sortierung:
[mm] (\bruch{7}{8})^{n} [/mm] < 1 < n log n < [mm] 2^{log(n)} [/mm] < [mm] n^{k} [/mm] < [mm] 2^n [/mm] < n!
Die Begründung fiel mir leicht bis auf den Fall, dass [mm] n^{k} [/mm] < [mm] 2^{n} [/mm] gilt.
Ich habe es folgendermaßen versucht
[mm] \limes_{n\rightarrow\infty} \bruch{n^{k}}{2^{n}} [/mm] = ?
bzw. per Induktion.
Kann mir hier jemand sagen, ob die Sortierung korrekt ist und wie ich das bei diesem speziellen Fall begründen kann?
Wenn Konstanten mit im Spiel sind, wie gehe ich damit am Besten um?
MFG
Alexander
|
|
| |
|
> Erstmal meine Sortierung:
>
> [mm](\bruch{7}{8})^{n}\ <\ 1\ <\ n*log\ n\ <\ 2^{\,log(n)}\ <\ n^{k}\ <\ 2^{\,n}\ <\ n![/mm]
>
> Die Begründung fiel mir leicht bis auf den Fall,
> dass [mm]n^{k}\ <\ 2^{n}[/mm] gilt.
>
> Ich habe es folgendermaßen versucht
>
> [mm]\limes_{n\rightarrow\infty} \bruch{n^{k}}{2^{n}}[/mm] = ?
>
> bzw. per Induktion.
>
> Kann mir hier jemand sagen, ob die Sortierung korrekt ist
> und wie ich das bei diesem speziellen Fall begründen kann?
>
> Wenn Konstanten mit im Spiel sind, wie gehe ich damit am
> Besten um?
>
> MFG
> Alexander
Hallo Alexander,
Die Einordnung $\ n*log\ n\ <\ [mm] 2^{\,log(n)}$
[/mm]
ist wohl verkehrt.
Ich nehme einmal an, dass log für den natürlichen
Logarithmus steht. Dann ist
$\ [mm] 2^{\,log(n)}\ [/mm] =\ [mm] \left(e^{log(2)}\right)^{\,log(n)}=\,\left(e^{log(n)}\right)^{\,log(2)}=\ n^{\,log(2)}=\ n^{0.693...}$
[/mm]
und dies ist natürlich "schwächer" als $\ n$ und auch
als $\ [mm] n*log(n)\,.$
[/mm]
Für den Vergleich der Potenzfunktion [mm] n^k [/mm] mit der
Exponentialfunktion [mm] 2^n [/mm] gibt es die Faustregel:
Eine Exponentialfunktion mit Basis > 1 ist
"stärker" als jedes Polynom. Um dies einzusehen,
kann man zunächst zwei Polynome unterschiedlichen
Grades vergleichen, zum Beispiel
[mm] f(x)=10^{100}*x^{99} [/mm] und [mm] g(x)=10^{-100}*x^{100}
[/mm]
Trotz dem eklatanten "Vorsprung" von f durch die
Vorfaktoren ist schlussendlich g "stärker" als f
wegen des um eins höheren Grades.
Betrachten wir dann die Exponentialfunktion
$\ [mm] f(n)=2^n=\left(e^{ln(2)}\right)^n=e^{n*ln(2)}=\summe_{i=0}^{\infty}\bruch{(n*ln(2))^i}{i\,!}=\summe_{i=0}^{\infty}\bruch{(ln(2))^i}{i\,!}*n^i$
[/mm]
Vergleicht man diese Funktion mit einer Potenzfunktion
[mm] p_k(x)=n^k [/mm]
mit einem noch so grossen Exponenten k, sieht man
leicht ein, dass [mm] p_k [/mm] niemals gegen f ankommen kann,
weil in der Entwicklung von f Glieder mit i>k und mit
positiven Koeffizienten stecken.
Konstante Faktoren spielen bei solchen Vergleichen
wohl nur dann eine Rolle, wenn die zu vergleichenden
Funktionen vom gleichen "O-Typ" sind. Beispiel:
von zwei Polynomen gleichen Grades n ist dasjenige
mit dem grössten [mm] a_n [/mm] (bzw. |an|) "stärker.
LG Al-Chwarizmi
|
|
|
|
