Aufwandsberechnung

[seaside]

Hallo,

kann mir vielleicht jemand anhand eines Beispiels erklären wie ich den Aufwand eines Algorithmus berechnen kann?

Ich finde leider im Netz keine guten Beispiele

loop1(n) {

m = 1;

i = 0;

while (m < n) {

while (i < m) {

i = i + 1;

}

m = m + i;

}

}

Vielen Dank für jede Hilfe

[lupo49]

Hier wird das ganz gut erklärt:

linux-related.de

[seaside]

Vielen Dank, die Seite war sehr hilfreich =)

Ich habe aber noch eine Frage zu folgenden Algorithmen:

loop5(n) {

m = n;

i = 4 * n;

while (i > 4) {

m = m + n;

i = i - 4;

}

while (m > 0) {

m = m - 2;

}

}

die erste Schleife wird nach meinen Überlegungen n- mal durchlaufen und die zweite 2n mal.

Die richtige Lösung ist jedoch O(n^2).

Werden die zwei Aufwandsklassen auch multipliziert wenn sie nicht verschachtelt sind?

loop2(n) {

if (n > 0) {

loop2(n - 500);

} else if (n < 0) {

loop2(n + 2);

}

}

Die Schleife terminiert nur für gerade Zahlen. Ich habe als Aufwandsklasse O(n) raus, kommt das hin?

Vielen Dank

[Klotzkopp]

die zweite 2n mal.

Das ist falsch. Bedenke, dass m bei jedem Durchlauf der ersten Schleife um n erhöht wird.