Laufzeiten
-
Guten Tag,
ich wollte fragen, ob jemand wüsste welche Laufzeit die folgende Operation hat.
doSomethingSimple(int n) {
while(n > 0) {
cout << "Something simple!" << endl;
n = n / 2;
}
}LG
Melis
-
@melisglfdn klar wüsste das jemand. Aber es ist ja deine Hausaufgabe.
-
@melisglfdn Wovon hängts denn ab? von
n
? O(n).
-
@Swordfish: O(n) ist aber nicht richtig...
-
@Th69 sagte in Laufzeiten:
@Swordfish: O(n) ist aber nicht richtig...
Das kann man so aber auch nicht sagen...
-
@Th69 Na schön. O(log n)
-
Vielleicht Overkill, aber ein klein wenig formaler:
Sei die Anzahl der Schleifendurchläufe und der Wert, den wir beim -ten Durchlauf berechnen:
( wegen Integer-Division, da )
Jetzt würde ich gerne wissen, für welche die Schleifenbedingung (
n > 0
) erfüllt ist, oder anders formuliert für welche meine Integer-Werte sind.Somit ist die Anzahl der Schleifendurchläufe kleiner oder gleich und die Komplexität liegt in . Könnte das passen?
-