Fachrat Informatik - Forum

Ich würde sagen so:

Um die Gleichheit zu beweisen, musst du zeigen, dass
1) 2^n = O(3^n)
und
2) 3^n = O(2^n)
.

1) ist gleichbedeutend mit:
Es gibt ein c, n0 Element von N, so dass für alle n>=n0 gilt: 2^n <= c * 3^n

Das ist z.B. für c = 1 und n0 = 1 erfüllt.

2)
Es gibt ein c, n0 Element von N, so dass für alle n>=n0 gilt: 3^n <= c * 2^n

Dies ist für kein c,n0 erfüllbar, da 3^n immer stärker wächst.


Also Widerspruch.




Alternativ geht glaube ich auch:

lim für (n-->Unednlich) (3^n) / (2^n) müsste eine Konstante ergeben damit die Klassen gleich sind.

Genau. Wenn f \in o(g(n)), dann folgt daraus g(n) \notin O(f(n)).

Quoted

Original von Arne
Genau. Wenn f \in o(g(n)), dann folgt daraus g(n) \notin O(f(n)).

Die lim Variante ist also ausreichend? Dann spart man sich das mit dem c, n0.

Die Argumentation über c und n0 ist hilfreich, wenn man zeigen will, das f \in O(g(n)) gilt, weil man dort dann eine Konstante und ein n0 angibt. Wenn man zeigen möchte, dass es nicht gilt, dann ist es nicht so sinnvoll zu sagen, es gibt eben kein c und n0, sodass das gelten kann (weil man da über unendliche Mengen Aussagen macht und es könnte ja dennoch vielleicht irgendein c und n0 geben...). Wenn ich jetzt zeige, dass es _echt_ schwächer wächst, also f \in o(g(n)) gilt, dann kann g ja nicht mehr in O(f(n)) sein, da es echt stärker wächst, als die O-Natation es "verkraften" tut.

ja