Die Groß-O Notation im worst case.

[BUG]

Erstmal den Link zu Wikipedia: http://de.wikipedia.org/wiki/Landau-Symbol

Dort findet man eine Definition für O( g ) ähnlich der folgenden:
f ∈ O(g) genau dann wenn http://upload.wikimedia.org/math/6/2...381ebc7386.png

Grafik frei übersetzt:
Es existiert ein c > 0 und ein x_0 so, dass für alle x > x_0 gilt |f(x)| <= c*|g(x)|
Ein solches c und x_0 findest du aber nicht für alle Kombinationen von f und g.

Beispiel 1:
Egal, wie (hoch) du c und x_0 wählst, es wird immer ein x >= x_0 geben, so dass |x²| > c*|x| (z.B. x = max(c+1, x_0+1) ).
Also ist gilt x² ∉ O(x)

Um zu zeigen das ein f ∈ O(g) ist, musst du ein x_0 und ein c finden, so dass die obige Definition zutrifft.

Beispiel 2:
Wir vermuten das 2x²+5x+6 ∈ O(x²) ist.

Also wollen wir ein x_0 und ein c > 0 finden, für das gilt:
|2x²+5x+6| < c*|x²| für alle x > x_0

Wir sehen, dass x besser nicht 0 sein sollte, also sagen wir: x_0 ist größer 0:
x_0 > 0

Als praktische Beigabe ergibt sich, dass die Terme in den Betragsstrichen jetzt immer positiv sind, d.h. können wir sie weglassen.

2x²+5x+6 < c*x²

Nun versuchen wir ein c zu finden für das die obige Ungleichung gilt:
2x²+5x+6 < c*x² # -2x²
5x+6 < (c-2)x² # /x² (geht problemlos, da x > x_0 > 0)
(5x+6)/x² < c-2
5/x + 6/x² < c-2
Nun setzen wir x_0 := 10, womit gilt 5/x + 6/x² < 1.
Jetzt suchen wir uns ein c, so dass c-2 >= 1, zum Beispiel c := 1 3

Damit haben wir ein x_0 = 10 und ein c = 1 gefunden, so dass |2x²+5x+6| < c*|x²| für alle x > x_0 gilt.
Also gilt laut Definition: 2x²+5x+6 ∈ O(x²)

So, ich finde, mehr sollte in der Infoklausur mathematisch nicht von euch verlangt werden

Ich hab das Ganze eigentlich nur geschrieben, weil du explizit N (=x_0) und C (=c) erwähnt hast,
fände soviel Mathematik in der 12. im Informatikkurs aber etwas merkwürdig
Bist du sicher, das du weißt, was euer Lehrer von euch will?

Disclaimer:
Ich hab mir zwar Mühe gegeben keine großartigen Fehler einzubauen, erhebe aber keinen Anspruch auf Korrektheit.
Falls jmd. Fehler findet, unbedingt melden (nicht dass mir das im März in der Klausur aufstößt ).

MfG,
Bug