Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Klausur 21.02.2008 - Aufgabe 9 O-Kalkül
Wer möchte Ergebnisse vergleichen?
a)
- O (log n)
- O (n²) → Hier hab ich allerdings keinen Schimmer was k bedeuten soll
- O (n²)
- O (n)
- O (n³)
b)
ja, ja, nein, ja
also a) hab ich genauso
und bei b hab ich:
ja, ja, nein, nein (wobei ich mir bei dem 2. ja nicht sicher bin).
Ah, stimmt hast recht, ich hab das n vor dem log übersehen!
bei der a)2) muss es glaube ich eher O(n) heißen, es steht nicht da was k ist → im Allgemeinen beschneidet k die eine Schleife → O(n). Rest passt.
bei der b) hätte ich gesagt, ja, nein, nein, nein, aber die zweite Angabe ist indeed etwas streitwürdig, wenn da das Element-Zeichen statt ‘=’ stehen würde wäre es wohl richtig, so wies dasteht ists aber imho falsch (kein Plan wie sies bewertet haben)
aber wurde nicht gesagt, dass es eigentlich immer das Elementzeichen beim O-Kalkül richtig ist, aber nur wiels handlicher ist = geschrieben wird?
Hier wird aber nicht das ∈ ersetzt, korrekterweie müsste es imho heißen: O(fg) ⊃ f * O(g). Aber so genau kenn ich mich damit auch nicht aus.
Warum ist es denn bei der b beim 4. nicht ja sondern nein, weil ich dachte in O(n) liegen auch alle anderen oberern Schranken, die größer sind als n oder? und n*logn ist doch immer größer als n (ab einem n) und dann wäre die Aussage doch richtig oder?
Ja eben. f(n) in O(g(n)) wenn fuer alle x : f(x) <= cg(n) (x->inf, c>0) und wie du schon gesagt hast ist nlog(n) > n also ist nlog(n) nicht in O(n), ergo ist O(nlog(n)) auch nicht echte Teilmenge von O(n), sonst muesste ja eine Funktion die in O(nlog(n)) liegt auch in O(n) liegen und das ist nicht der Fall. (EDIT: Anders herum gilt es z.B. was in O(n) liegt liegt auch automatisch in O(nlog(n)))
Aber auf Folie 5-24c) im Skript steht doch dass die Aussage stimmt? Und damit wäre Ausage 2 von b) doch richtig!
ah cool danke 
Vorsicht, so wies im Script: O(f(n))*O(g(n)) = O(f(n)*g(n)) ist es auch richtig, aber in der Klausur stand es ja O(f(n)*g(n)) = f(n)*O(g(n)), was imho formal falsch ist (auch wenn es gut sein kann, dass sie das als richtig interpretiert haben, kA).