Funktionen ordnen (hoch zu niedrig):
Code: Alles auswählen
(n+1)!
1.337*(n^3)
2^n
log(n)^(7/2)
log(n)^(log log n)
sqrt(n)
log(n^2)
e^(log log n^2)
sqrt(log n)
log log n
42^42
1
Komplexitätenquiz: da habe ich noch nichts!
Moderator: Algorithmen und Datenstrukturen
Code: Alles auswählen
(n+1)!
1.337*(n^3)
2^n
log(n)^(7/2)
log(n)^(log log n)
sqrt(n)
log(n^2)
e^(log log n^2)
sqrt(log n)
log log n
42^42
1
Hab mir jetzt nicht alles genau angeschaut, aber du musst auf jeden Fall 2^n und 1.337*(n^3) vertauschen, das letzteres polynomiell ist. Zudem müssen glaube ich auch log(n)^(7/2) und log(n)^(log log n), da (7/2) lediglich eine Konstante ist.paprikawuerzung hat geschrieben:Hat jemand Lösungen für die Aufgaben im Anhang? Ich hätte:
Funktionen ordnen (hoch zu niedrig):Code: Alles auswählen
(n+1)! 1.337*(n^3) 2^n log(n)^(7/2) log(n)^(log log n) sqrt(n) log(n^2) e^(log log n^2) sqrt(log n) log log n 42^42 1
Ja, alle oben aufgelisteten Funktionen sind in O(n!).paprikawuerzung hat geschrieben: Frage: stimmt es, dass es \(1.337*(n^3) \in O(n!)\) ist?
Ich würde jetzt auf die schnelle sagen:paprikawuerzung hat geschrieben: Komplexitätenquiz: da habe ich noch nichts!
Ah, es sollte eigentlich 1.337^(n^3) heißen! Dann sind beide exponentiell.yokop hat geschrieben: Hab mir jetzt nicht alles genau angeschaut, aber du musst auf jeden Fall 2^n und 1.337*(n^3) vertauschen, das letzteres polynomiell ist.
Ja, die Umformung stimmt. Also müsste es auch asymptotisch gleich sein.yokop hat geschrieben: Zudem müssen glaube ich auch log(n)^(7/2) und log(n)^(log log n), da (7/2) lediglich eine Konstante ist.
Eigene Frage zu e^(log log n^2), ist diese Umformung Unfug ?
e^(log log n^2) ist asymptotisch äquivalent zu e^(ln ln n^2) = ln(n^2) was aymptotisch gleich zu log(n^2) ist.
Ich stimme bei allen zu außer:yokop hat geschrieben: Komplexitätenquiz: da habe ich noch nichts!
Ich würde jetzt auf die schnelle sagen:
Für f(n) = n^2.71, in O,Ω und Φ
f(n) = log2(2n) in O,Ω und Φ
f(n) = n^5 + n^4 + 42 in O
f(n) = log2(2n) in O,Ω und Φ
f(n) = n^(log c) in 0
f(n) = 2^n in Ω
f(n) = e^(ln e) in O
f(n) = (n+1)! in Ω
Ja stimmtpaprikawuerzung hat geschrieben: f(n) = 2^n im Vergleich mit (2^(n/2)): da würde ich auch sagen O,Ω und Φ!
Ich dachte mir: log2(log12(144^n)) = log2(log12(12^2n)) = log2(2n)paprikawuerzung hat geschrieben: f(n) = log2(2n) im Vergleich mit g(n) = (log2 log12 144^n): da würde ich sagen nur O, da nicht \(lim\ sup\ \frac{f(n)}{g(n)} < \infty\) ist.
Sagt jedenfalls Wolfram Alpha: http://www.wolframalpha.com/input/?i=li ... y&dataset=