Wie berechne ich die Laufzeit richtig (Programmieren)?
Ich habe etwas Schwierigkeiten bei der Berechnung der Laufzeit. Das Thema verwirrt mich bisschen, obwohl es nicht so schwer ist.
Unten stehen meine Erklärungen, wäre lieb, ihr das Feedback zurücklasst.
while i <= n // gehen Sie davon aus, dass i=j<n ist
if i mod 3 = 0
print(i)
i++
for i = a to n (n ausschließlich)
for j = 2 to 4 (4 ausschließlich)
if j * i gerade
print(j, i)
Erklärungen:
while i <= n // gehen Sie davon aus, dass i=j<n ist
Hier wird die komplette Schleife durchlaufen, deswegen ist das 0(n)
if i mod 3 = 0
print(i)
i++
Hier bin ich mir unsicher:
Die Anzahl der Durchläufe ist zwar abhängig von i aber, es werden nicht alle Elemente durchlaufen.
for i = a to n (n ausschließlich)
O(n) gleiche begründung wie davor.
for j = 2 to 4 (4 ausschließlich)
if j * i gerade (Unsicher)
print(j, i)
O(1) weil die Schleife nicht komplett durchlaufen wird.
1 Antwort
O(1) weil die Schleife nicht komplett durchlaufen wird.
Wird die immer nicht komplett durchlaufen? Bei ner laufzeit geht man immer vom worst case aus. Ne schleife von x bis n hat immer ne laufzeit von O(n)
Ne geschachtelte schleife die beide von x bis n gehen haben immer ne Laufzeit von O(n²) Weil man maximal n * n durchläufe hat.
Ist die innere schleife fix. hat man ggf. 4 * n durchläufe. Was imgrunde auch O(n) ist. Obs nun 4n ist oeder 5000n ist eher unwichtig. Es geht um die Lineare abhängigkeit.
Für O(1) muss der code egal wie und mit welchen parameter er aufgerufen wird immer in einer festen anzahl von schritten enden. Ne feste for schleifen z.b. von 0-7 hat die laufzeit von O(1) weil die immer in 8 schritten durch ist. Egal welche parameter du hast.
Und wenn du in unterabschnitten verschiedenen Laufzeiten hast ist die Gesamtlaufzeit immer die Größtmögliche.
N ausschließlich bedeutet nach meinem Verständnis das die Schleife mit dem Wert X= n nicht mehr durchläuft.
Sagen wir wir haben ne schleift von I=0;I<n;I++
Dann ist das grösste I das in der Schleife benutzt wird n-1. N selbst ist hier ausgeschlossen.
N-1 ist aber weiterhin von n abhängig. Daher ist das Laufzeit verhalten immer noch O(n) und nicht O(1)
Zu:
Wird die immer nicht komplett durchlaufen? Bei ner laufzeit geht man immer vom worst case aus. Ne schleife von x bis n hat immer ne laufzeit von O(n)
In der Aufgabe steht in Klammern (n ausschließlich)
So wie ich das verstanden habe heißt das, dass der Durchlauf nicht folgt, deswegen dachte ich es sei konstant.