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

Bei Postings zu Aufgabe Nr. x auf Blatt Nr. y lassen Sie Ihr Betreff bitte mit "y.x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Aufgabe Nr. x auf Blatt Nr. y lassen Sie Ihr Betreff bitte mit "y.x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
paprikawuerzung
Mausschubser
Mausschubser
Beiträge: 80
Registriert: 23. Mär 2014 23:33

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

Beitrag von paprikawuerzung » 17. Sep 2016 16:28

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!
Dateianhänge
Screen Shot 2016-09-17 at 16.22.47.png
Screen Shot 2016-09-17 at 16.22.47.png (182.41 KiB) 459 mal betrachtet

yokop
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 13. Apr 2016 12:49

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

Beitrag von yokop » 17. Sep 2016 16:56

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
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.
paprikawuerzung hat geschrieben: Frage: stimmt es, dass es \(1.337*(n^3) \in O(n!)\) ist?
Ja, alle oben aufgelisteten Funktionen sind in O(n!).
paprikawuerzung 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 Ω

paprikawuerzung
Mausschubser
Mausschubser
Beiträge: 80
Registriert: 23. Mär 2014 23:33

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

Beitrag von paprikawuerzung » 17. Sep 2016 17:26

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.
Ah, es sollte eigentlich 1.337^(n^3) heißen! Dann sind beide exponentiell.
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.
Ja, die Umformung stimmt. Also müsste es auch asymptotisch gleich sein.
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 Ω
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
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 13. Apr 2016 12:49

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

Beitrag von yokop » 17. Sep 2016 17:35

paprikawuerzung hat geschrieben: f(n) = 2^n im Vergleich mit (2^(n/2)): da würde ich auch sagen O,Ω und Φ!
Ja stimmt :)
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=
Ich dachte mir: log2(log12(144^n)) = log2(log12(12^2n)) = log2(2n)

Antworten

Zurück zu „AuD: Theoretische Aufgaben“