Komplexität und O-Notation

[breakdownfever]

Hallo,

da ich ein bisschen überfragt bin mit theoretischen Java-Fragen und um zu wissen ob ich das Thema mit dem Aufwand richtig verstanden habe, wollte ich kurz mal fragen ob meine Lösung so richtig ist.

In dieser Übung sollten wir den genauen Aufwand und den Aufwand in O-Notation für folgende for-Schleife angeben, wobei x++ den Aufwand O(1) hat und Verwaltungsaufwand nicht berücksichtigt wird.

 for (int i=n; i>1; i/=3) 
x++;

Da es sich um ein Integer handelt, wird die Schleife maximal n/3 mal ausgeführt. Dementsprechend wäre der genaue Aufwand bei

 n/3 * O(1)

und der Aufwand in O-Notation

 1/3 * n * O(1) => 1/3 * O(n) => O(n)

da Konstanten ja weggelassen werden.

Das Thema genauer Aufwand wurde im Skript jedoch auch nicht behandelt und die Beispiele sehr Basic gehalten. Ich bin mir recht sicher, dass meine O-Notation richtig ist nur kann ich mit dem Begriff "genauem Aufwand" nicht wirklich anfangen. Ich hoffe ihr könnt mir weiterhelfen.
Grüße

 

[njans]

Genauer Aufwand? So habe ich den Begriff noch nicht gehört, aber es könnte Theta damit gemeint sein. Während die groß O Funktion dir den WorstCase angibt, gibt Theta den genauen Aufwand an, siehe Wikipedia.

P.S. dein O(n) für deine Schleife würde ich als richtig erachten.

 

[qwert]

Ich möchte einwerfen, dass der Aufwand O(n) für die Schleife keinesfalls richtig ist. Die Schleife wird nicht (n/3)-mal ausgeführt, sondern log3(n)-mal!