zeitkomplexität !

dcom · Anmeldungsdatum: 03.07.2005 Beiträge: 3

hi @ all !
ich hab mal ne frage zur zeitkomplexität von schleifen !

hier erstmal der code :
for(i=5;i<n*n;i++){
i=i+1;
for(j=0;j<i;j++){
a=sqrt(c*c - b*b);
}
}

meine frage ist jetzt wie die komplexität von dem gesamten programm ist !
meiner meinung nach ist die erste schleife ja n^2/2 und die zweite ist n !
ist jetzt die gesamte n^3/2 oder nur n^2 oder wie soll ich das verstehen !
bei verschachtelten schleifen werden die komplexitäten ja multipliziert !

ED209 · Anmeldungsdatum: 30.05.2005 Beiträge: 122

Mal abgesehen davon, dass ich den Code ziemlich unsinnig finde (man koennte ihn umschreiben und haette eine feste Laufzeit ohne am Ergbenis was zu aendern), werden bei der Laufzeit normalerweise konstante Faktoren ignoriert.
Demnach musst du nicht staendig durch zwei teilen. Aber an sich scheinen deine Ueberlegungen zu stimmen.

dcom · Anmeldungsdatum: 03.07.2005 Beiträge: 3

also wenn ich dann alle konstanten weglasse hab ich doch eine komplexität von n^3 oder ? denn die erste schleife läuft ja bis n*n also n^2 !
und n^2 wäre es doch nur wenn die erste schleife nur bis <n laufen würde !
also erste schleife (n*n) mal zweite schleife (n) = n^3 ?
oder doch n^2 ?
ich bin etwas verwirrt ...

ED209 · Anmeldungsdatum: 30.05.2005 Beiträge: 122

ich weiss nicht wie du auf n^2 als Endergebnis kommst, n^3 ist durchaus richtig.

Crotaphytus · Anmeldungsdatum: 08.05.2005 Beiträge: 213

Allerdings schätze ich, dass bei der Aufgabe auch der Weg interessant sein dürfte, einfach nur als Ergebnis n³ angeben dürft wohl nicht reichen...

dcom · Anmeldungsdatum: 03.07.2005 Beiträge: 3

also ich hab mir das nochmal angesehen und habe festgestellt das n^3 doch nicht richtig ist !
denn die zweite schleife wird ja nicht n-mal durchlaufen sondern läuft bis i (und i laüft bis n*n) - also ist die richtige antwort n^4 !

Crotaphytus · Anmeldungsdatum: 08.05.2005 Beiträge: 213

Du hast Recht! Peinlich, peinlich...

(Wer baut aber auch so ne dämliche Funktion... Augenzwinkern

)