O Kalkül 31.07.2008

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.

O Kalkül 31.07.2008
Aufgabe 9
Sind meine Ergebnisse richtig? Wenn nein, warum nicht? Ich hab:
a)

  1. O(n)

  2. O(n²)

  3. O(n²)

  4. O(n * log n)

  5. O(n²)

b)

f: O(1)

fac: O(n)

hanoi: O(n)

c)

  1. keine ahnung
  2. ja

9a.1: O(n)
9a.2: O(n²)
9a.3: O(n²)
9a.4: n * log n
9a.5: O(n)

9b.1: O(1)
9b.2: O(n)
9b.3: O(x^n)

9c.1: Nein
9c.2: Ja
:slight_smile:


Die a hab ich identisch gelöst.

Bei der b hab ich beim ersten auch O(1).
fac und hanoi weiß ich nicht, wie man die löst. Ebenso die c1. Kann das jemand mal erklären bitte?

Bei der c2 hatte ich auch ja.


fac():
Bei jedem Rekursionsschritt vermindert sich der Parameter um 1 und fac() mit dem verminderten n einmal aufgerufen.
=> Es wird also n-mal die fac() Methode aufgerufen => O(n)

hanoi():
Der Methode hanoi wird der Parameter n übergeben.
Jeder Aufruf der Methode hanoi() resultiert in 2 weiteren Aufrufen (Stichwort: exponentiell) mit einem um 1 verminderten n.
=> O(x^n) (Zeichne einfach mal den Baum, das hilft oft :wink: )


Unter der Gefahr eine dumme Frage zu stellen:
Warum steht da überhaupt void f(int n) und dann return …;? Seid ihr davon ausgegangen dass es sich um einen Druckfehler handelt und es heißen müsste int f(int n) { return …;}? Frage mich die ganze Zeit ob das ne Fangfrage ist :nuts:


sieht mir nach nem Fehler in der Angabe aus


Es ist glaub ich kein Angabenfehler (siehe Kapitel 8 Seite 29).

warum habt ihr eigentlich alle bei der 9b.3 O(x^n). Müsste das x nicht gleich 2 sein?
Also 9b.3: O(2^n).


Was hat die Fibonacci-Funktion mit einem falschen return-Typ (void statt int) zu tun?


Stimmt stimmt! Hab erst jetzt das void gesehen. xD


for (int i = 0; i < n; i++)
for (int j = 0; j < i; j++)
f(i,j);

steh gerad auf den Schlauch warum O(n²), i ist doch immer kleiner n :\


Du kannst dir ueberlegen, wie oft f(i,j) aufgerufen wird.
Das ist 0 mal fuer i=0, 1 mal fuer i=1, 2 mal fuer i=2…

f(i,j) wird also 0+1+2…+(n-2)+(n-1) mal aufgerufen. Gemaess Gauss’scher Summenformel kann man das reduzieren auf ((n-1)*n)/2. Nun kann man anhand der Rechenregeln im O-Kalkuel auf O(n^2) vereinfachen. (Angenommen f(i,j) kann man in O(1) berechnen.)


Ich hänge noch bei der hanoi Methode.
Kann das jemand nochmal genauer erklären, wie man da auf x^n kommen soll?


Ich hoffe mal das void war keine Fangfrage, aber ich haette das einfach ignoriert. Weil so wuerde es ja gar nicht kompilieren.

Muesste die a5) nicht O(n) sein? Weil es werden jedesmal 10 Schritte (von i bis i+10) ausgefuehrt.

Bei Hanoi hab ich auch O(2^n).


Natürlich. Tuchkata hat das oben ja auch schon richtig erkannt.