Frage zu Laufzeitkomplexität

Computer: Software & Programmierung Programmierung allgemein
#1

Hallo ihr Experten,

ich soll Laufzeitkomplexitäten bestimmen, habe jedoch festgestellt das ich das bisher falsch gemacht habe und habe nun zu der richtigen Läsung eine Frage.
Hier zuerst einmal die Aufgabe mit entsprechender Lösung:

r:=0; für r:=0,a:= 0 ist es 2,da 2 Operatoren
a:=0;
while a ungleich n do 3n+1 (äußere Schleife und der Abbruch)
a:= a+1;
b:= b+1;
while b ungleich a do 3*(1+2+…+n)+n diesen Schritt verstehe
r:= r +1; ich nicht
b:= b+1;
end;
end;

Ergebnis dann: 3+4n+3*n*(n+1)/2
1,5n²+5,5n+3
Laufzeitkomplexität: n²

ich verstehe jedoch den Schritt der zweiten Schleife nicht. Kann mir da einer von euch erklären,wie ich das mache?

Liebe Grüße von der sich fragenden Vicky

#2

Hallo Vicky,

unter der Annahme, dass es vor der inneren Schleife „b:=0;“ und nicht „b:=b+1;“ lautet, wird die inner Schleife nicht n mal n Aktivitäten erzeugen, sondern im ersten Durchlauf der äußeren Schleife 1 Aktivität, im zweiten 2 usw. usf.
Das ist durch ( 1 + 2 + … + n ) ausgedrückt.

Kommst Du damit selber weiter?

Gruß
Volkmar

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]