Die Groß-O Notation im worst case.

[Kanikkl]

Guten Morgen,

ich schreibe am Montag meine 2. Informatik Klausur in der 12 und wir werden sehr wahrscheinlich über die Groß O Notation in worst case schreiben. Wir haben uns vorher gemeinsam schon eine Probeklausur angeschaut und besprochen wo es Probleme gibt, und ich war so Klug und dachte ich hätts mir aufgeschrieben, was dann nicht der Fall war Wie es halt so ist

Nun denn, was die Groß O Notation ist und wozu man sie benötigt weiß ich ganz genau, auch wie man f(n) aufstellt ist mir bewusst, aber wie führe ich jetzt den Vergleich von f(n) zu O(g(n)) durch? Was mich auch etwas gestört hat, war, dass man die Konstante C und die Konstante N frei wählen kann... (Das ist doch Blödsinn, ist dann doch kein Vergleich mehr... oder etwa nicht?)

Und wie bestimme ich, ob die Methode zur Klasse O(n) oder O(n²)

[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

[Kanikkl]

Vielen Dank erst einmal für deine Ausführliche antwort...

was ich aus deiner Definition verstanden habe ist folgendes:

-> Wenn man herausfinden will, zu welcher Klasse gehört, muss man die Gleichung f(n) zu c*n oder c*n² (oder c*n³) kleiner setzen : f(n)<c*n²
-> Wenn man ein C und ein X_0 ermitteln kann, dann kann man sicher davon ausgehen, dass sie zur Klasse O(n²) gehört..

-> Explizit gilt für die Rechnung: erst einmal durch die Klasse teilen, in die man die Gleichung vermutet: z.b. /n oder /n² Und dafür gilt, dass n > 0 sein muss.

Hab aber ein paar Fragen zu

Zitat:

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

- Wieso sagt man x_0 und setzen wir für x_0 eine beliebige Zahl ein, damit f(n) (müsste ja eig f(x) heißen *g*) möglichst klein ist und x > 0 erfüllt ist?


-----

Und genau so viel brauchen wir auch Wenn du mir meine offen Frage noch beantworten würdest, wär das super ^^

[BUG]

Zitat von Kanikkl:

-> Explizit gilt für die Rechnung: erst einmal durch die Klasse teilen, in die man die Gleichung vermutet: z.b. /n oder /n² Und dafür gilt, dass n > 0 sein muss.

Muss nicht sein, könnte aber für Polynome ein ganz vernünftiges Mittel sein (ich weiß es nicht genau Rechne einfach ein paar Übungsaufgaben.). Hatte sich hier eben angeboten. Wähle die Einschränkungen für n bzw. n ganz konkret immer so das das Ganze überschaubarer wird (zB. Weglassen der Betragsstriche, Teilen durch x > n > 0 durch in Ungleichungen möglich).

Zitat:

Jetzt suchen wir uns ein c, so dass c-2 >= 1, zum Beispiel c := 1

Ha, Fehler gefunden, sollte c := 3 heißen (war etwas spät ), denn (1-2) ist natürlich nicht größergleich 0

Zitat von Kanikkl:

- Wieso sagt man x_0 und setzen wir für x_0 eine beliebige Zahl ein, damit f(n) (müsste ja eig f(x) heißen *g*) möglichst klein ist und x > 0 erfüllt ist?

X_0 = n habe ich es nur genannt, weil das oben so in der Grafik steht.
Wichtig ist: Die Ungleichung muss für jedes x > n gelten

Im Grunde musst du immer nur zeigen dass ein N und c existieren, so dass die Ungleichung erfüllt ist
(wenn du es wie ich machen willst: achte auf äquivalente Umformungen für Ungleichungen).
Es ist für den Lehrer vermutlich bloß besser nachvollziehbar, wenn du konkrete N und c wählst.
Wie du dazu kommst ist egal.
Im Grunde könntest du ein passendes N und c raten (macht sich in Klausur nicht so gut, ich weiß).


MfG,
Bug

[Kanikkl]

Jo das mitm Raten ist auf jeden Fall ein Problem.

Ich werd dann mal ein paar Beispiele durch arbeiten sollte kein Problem sein, vielen Dank soweit.

Am besten mach ich mir nen Spicker, mit den einzelnen Schritten und den Bedingungen