Guru
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
O(n) ist ja grob gesagt die Klasse aller Funktionen, die nach oben durch die Funktion f(n) = n "beschränkt" sind. 2^{O(n)} ist dann die Klasse aller Funktionen der Form 2^(g(n)), wobei g eine Funktion aus der Klasse O(n) ist.Quoted
Original von Neo
Was bedeutet es, wenn O(n) im Exponenten steht?
This post has been edited 1 times, last edit by "Joachim" (Feb 9th 2007, 12:18pm)
Guru
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
DIe Laufzeit ist nicht zwingend exponentiell, denn 2^{log2(n)} ist ja auch in der Klasse 2^{O(n)} enthalten.Quoted
Original von Neo
Das heißt, dass eine Funktion, deren Laufzeit durch 2^O(n) nach oben hin
beschränkt ist, exponentielle Laufzeit besitzt.
Das reicht als Begründung nicht. 2^{n^3} wächst asymptotisch "echt stärker" als jede Funktion aus 2^{O(n)}; das läßt sich über die Definition der O-Notation beweisen.Quoted
Somit trifft die Aussage aus Aufgabe 1h) nicht zu. Denn n^3 wächst kubisch
mit der Länge der Eingabe, Funktionen der Klasse O(n) dagegen linear.
Guru
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Direkt läßt sich das vermutlich nicht übertragen.Quoted
Original von Neo
Nach der Definition von O gibt es Funktionen f und g,
so dass gelten muss:
f=O(g), falls f(n) <= c * g(n)
Gilt diese Definition Analog auch für
2^f = 2^O(g), falls 2^f(n) <= c* 2^g(n)
This post has been edited 1 times, last edit by "Joachim" (Feb 11th 2007, 2:33pm)