(ln n)^(ln n) vgl mit 2^(ln n) < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Ordne folgende Funktionen so, dass für zwei in der Anordnung aufeinanderfolgende Funktionen f und g gilt: f [mm] \in [/mm] o(g) oder [mm] f\in [/mm] O(g) gilt. Beweise deine Anordnung! Benutze gfs. Monotonieeigenschaften der Funktionen ohne Beweis.
[mm]
f1(x)= n [/mm]
[mm]
f2(x) = (ln n)^{ln n} [/mm]
[mm]
f3(x) = (log n^2)^2[/mm] |
was mir persönlich an Dingen eingefallen ist, was mir helfen könnte:
1. "wächst langsamer als", von links nach rechts:
1, log n, n, n log n, [mm] n^2, 2^n, [/mm] n!, [mm] n^n
[/mm]
2. manche Funktionen sind nicht vergleichbar , wenn wir annehmen das die Funktionen f1-f4 alle vergleichbar sind, dann gäbe es 4! Vergleiche. (so interpretiere ich die Aufgabenstellung )
3. log n ist der Logarithmus zu einer Basis, die nicht näher beschrieben ist
4. f1 [mm] \in [/mm] O(g1) [mm] \wedge [/mm] f2 [mm] \in [/mm] O(g2) => f1*f2 [mm] \in [/mm] O(g1*g2) (hilft vielleicht bei Ansatz 4.)
Meine Ansätze:
1. Vergleich f2 und f3:
Behauptung: f3 in o(f2)
Beweis:
[mm] (logn^2)^2 [/mm] < c* (ln [mm] n)^{ln n}
[/mm]
(2logn)*(2logn) < (c* ln n * c* ln n * c* ln n ...) (genau ln n (floor) mal)
d.h. sobald ln n > 2 ist, stimmt es dass f3 gewinnt. q.e.d
das muss ich mit dem lim(f3/f2) zeigen,richtig?
3. Vergleich von f1 und f2
Behauptung: f1 in o(f2)
Beweis:
[mm] 2^{ln n} [/mm] < c* (ln n) ^{ln n}
Grund: Exponent ist gleich d.h. ich kann die Frage zurückführen auf
2 < c* ln n
und das ist der fall, da eine konstante immer groß O einer Funktion ist.
ebenso wie bei Vergleich 2
4. Vergleich f1 und f3:
Behauptung: f3 [mm] \in [/mm] o(f2)
(log [mm] n^2)^2 [/mm] < c* n
(2log [mm] n)^2 [/mm] <= c* n
2*(log n) * (logn) <= c * n
hmm wenn ich 4. ins Gedächtnis rufe, dann kann ich per Gegenteilsbeweis vielleicht folgern, dass
n < c * 2*(log n) * (logn) gilt. Ratschläge?
Grüße aus München
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:20 Sa 12.12.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
