Laufzeitverhalten

[LegendaryBeazt]

Wir haben vor kurzen das Thema Laufzeiten behandelt und sollen als Hausaufgabe die Laufzeiten verschiedener Abschnitte bestimmen.
Der letzte Abschnitt verwirrt mich einbisschen.

for(intj=0;j<n;j++) {
for(inti=n;i>1;i=i/2) {
System.out.println(i)
}
}

Bei Schleifen beträgt die Laufzeit immer n. Sind sie verschachtelt wie im Beispiel ist sie n hoch 2, bei 3 Scheifen n hoch 3 usw.
Aber hier läuft die äußere Schleife doch n-mal und die innere nur n/2 mal.
Schreibt man trotzdem n hoch 2 (also O(n hoch2 ) in der O-Notation) als Laufzeit, weil es 2 verschachtelte Schleifen sind?
Oder ist die O-Notation O(n / (n/2))?

 

[LimDul]

O(n/(n/2)) ergibt keinen keinen Sinn - das wäre konstante Laufzeit n : (n/2) = 2 = Konstante Laufzeit - und das ist mit Sicherheit falsch.

Die innere Schleife läuft aber auch nicht n/2-mal (pro äußeren Durchlauf). Wenn n = 16 ist, wie oft läuft sie dann? Da i immer halbiert wird, läuft sie dann 4 mal. Das heißt, sie läuft Wurzel(n) pro Durchlauf - oder n^(1/2).

Ergibt als gesamt Laufzeit: n*n^(1/2)=n^(3/2), also O(n^(3/2)).

 

[httpdigest]

Das heißt, sie läuft Wurzel(n) pro Durchlauf - oder n^(1/2).

Das ist nicht korrekt. Die innere Schleife läuft `O(log₂(n))`, da der Schleifenzähler `i` immer halbiert wird.
Somit ist die Gesamtlaufzeit: O(n · log₂(n))

 

[LimDul]

Arg, zu lange her mein Studium

Stimmt natürlich.