Fachrat Informatik - Forum

Quoted

Original von Neo
Was bedeutet es, wenn O(n) im Exponenten steht?

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
Das heißt, dass eine Funktion, deren Laufzeit durch 2^O(n) nach oben hin
beschränkt ist, exponentielle Laufzeit besitzt.

DIe Laufzeit ist nicht zwingend exponentiell, denn 2^{log2(n)} ist ja auch in der Klasse 2^{O(n)} enthalten.

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.

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

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)

Direkt läßt sich das vermutlich nicht übertragen.

O(n) ist eine Klasse von Funktionen. "f(n) = O(n)" ist eigentlich als "f(n) \in O(n)" zu lesen und bedeutet daher daß die Funktion f in der Klasse O(n) enthalten ist.

2^{O(n)} ist dann ebenfalls eine Klasse von Funktionen. Und zwar gilt 2^{O(n)} = {g | es gibt eine Funktion f aus der Klasse O(n), so daß g = 2^f gilt}.

Üblicherweise meint man mit 2^{...} sogar die Klasse O(2^{...}), da es bei Exponentialfunktionen sowieso nicht mehr auf Vorfaktoren und Summanden ankommt. (Ich gebe zu, daß der Aufgabenzettel bei dieser Aufgabe nicht besonders präzise ist. Bei der Erstellung der Aufgaben damals habe ich aber angenommen, daß die O-Notation ausführlich bereits in der Veranstaltung "Datenstrukturen und Algorithmen" behandelt wurde, also daß inbesondere Schreibweisen wie 2^{O(...)} bekannt sind.)

So, nun also zurück zur ursprünglichen Frage: Gilt 2^{n^3} = 2^{O(n)}? Dies ist (mit den obigen Erläuterungen) äquivalent zur Frage, ob die Funktion 2^{n^3} in der Klasse O(2^{O(n)}) enthalten ist. Dies ist nicht der Fall. Denn 2^{n^3} / 2^{k * n + c} ist gleich 2^{n^3 - k * n - c}, was für jedes Paar von Konstanten k und c gegen unendlich strebt.