Eine Frage zu Laufzeitkomplexität.

fb18.de / Diplom Informatik / Unterbereich Grundstudium / Formale Informatik

Eine Frage zu Laufzeitkomplexität. 2006-02-05 15:55

Anonymer User

Kann jemand mir sagen ,wie man die Laufzeitkomplexität dieses Algorithmus berechnen?Danke.

r := 0;
a := 0;
while a ≠ n do
a := a+1;
b := 0;
while b ≠ n do
r := r+1;
b := b+1;
end;
end;

Re: Eine Frage zu Laufzeitkomplexität. 2006-02-05 16:27

georg

Unter der Annahme, dass mit '?' hier [img]http://mokrates.de/cgi-bin/texstring?%5Cle[/img]
gemeint ist, würde ich sagen: [img]http://mokrates.de/cgi-bin/texstring?O((n%2B1)%5E2)[/img].
Im Fall ?=< wäre mein Tip [img]http://mokrates.de/cgi-bin/texstring?O(n%5E2)[/img].

Re: Eine Frage zu Laufzeitkomplexität. 2006-02-05 16:31

Viciarg

Es ist [img]http://mokrates.de/cgi-bin/texstring?%5Cneq[/img].

Re: Eine Frage zu Laufzeitkomplexität. 2006-02-05 16:32

georg

Dann ist das Ergebnis das gleiche wie bei ?=<.

Re: Eine Frage zu Laufzeitkomplexität. 2006-02-05 17:59

Zaphod

Kann jemand mir sagen ,wie man die Laufzeitkomplexität dieses Algorithmus berechnen?Danke.

Kann man das überhaupt angeben, wenn nichtmal als Präkondition angegeben ist, dass n eine natürliche Zahl ist? Sonst terminiert das nämlich gar nicht…

Ansonsten sieht der Code etwas lesbarer aus, wenn du das CODE-Tag benutzt:


r := 0;
a := 0;
while a &#8800; n do
   a := a+1;
   b := 0;
   while b &#8800; n do
      r := r+1;
      b := b+1;
   end;
end;

Re: Eine Frage zu Laufzeitkomplexität. 2006-02-14 21:12

Anonymer User

Unter der Annahme, dass mit '?' hier [img]http://mokrates.de/cgi-bin/texstring?%5Cle[/img]
gemeint ist, würde ich sagen: [img]http://mokrates.de/cgi-bin/texstring?O((n%2B1)%5E2)[/img].
Im Fall ?=< wäre mein Tip [img]http://mokrates.de/cgi-bin/texstring?O(n%5E2)[/img].

Das ist doch das Selbe, denn (Oh-Notation!) [img]http://mokrates.de/cgi-bin/texstring?O((n%2B1)%5E2)%20%3D%20O(n%5E2)[/img].
Also nicht anfangen Erbsen zu zählen, wenn's um ganze Kisten davon geht…