T3.1 und 2 (2015): Funktionen ordnen/Komplexitätenquiz

[paprikawuerzung]

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

Frage: stimmt es, dass es \(1.337*(n^3) \in O(n!)\) ist?

Komplexitätenquiz: da habe ich noch nichts!

[yokop]

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

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.

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.

Frage: stimmt es, dass es \(1.337*(n^3) \in O(n!)\) ist?

Ja, alle oben aufgelisteten Funktionen sind in O(n!).

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 Ω

[paprikawuerzung]

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.

Ah, es sollte eigentlich 1.337^(n^3) heißen! Dann sind beide exponentiell.

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.

Ja, die Umformung stimmt. Also müsste es auch asymptotisch gleich sein.

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 Ω

Ich stimme bei allen zu außer:
f(n) = 2^n im Vergleich mit (2^(n/2)): da würde ich auch sagen O,Ω und Φ!
und
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=

[yokop]

f(n) = 2^n im Vergleich mit (2^(n/2)): da würde ich auch sagen O,Ω und Φ!

Ja stimmt

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=

Ich dachte mir: log2(log12(144^n)) = log2(log12(12^2n)) = log2(2n)