Warum hat dieser einfache Algorithmus lineare Laufzeit?

[babuschka]

Hallo zusammen!

Warum hat der folgender Algorithmus worst-case Komplexität O(n), also lineare Laufzeit? Ich komme einfach nicht drauf. Dabei liefern rand(0,n) eine Zufallszahl zwischen 0 und n. Wie kann man das nur begründen?

stack <-- create()
for i <-- 1 to n do
    push(stack,a_i)
    j <-- rand(0,n)
    while not empty(stack) and j>0 do
        pop(stack)
        j <-- j-1
    endwhile
endfor

Ich würde es sehr begrüßen, wenn jemand einen Tipp für mich hat bzw. mir helfen könnte!! Vielen Dank.

squirrel

 

[Redfrettchen]

Hi,
imho hat das Programm eine worst-case-Komplexität von O(n²).
Das Programm besteht hauptsächlich aus einer for-Schleife, die immer n-mal durch läuft. Im Inneren der Schleife gibt es noch eine while-Schleife, die in Abhängigkeit von i (dem Index der for-Schleife) maximal durchlaufen wird. Denn ist i=1, dann wird die while-Schleife maximal 1 mal durchlaufen.
Wir haben als im schlechtesten Fall 1+2+3+4+5+...+n=n*(n+1)/2 Durchläufe der while-Schleife während der gesamten Programmausführung, also eine Zeitkomplexität von O(n²).
Bei der Speicherkomplexität ist es zwar genau andersherum: Je öfter die innere while-Schleife durchläuft, desto weniger müssen wir speichern, aber der Speicher-worst-case hat nur eine Komplexität von O(n), weil maximal n Elemente gespeichert werden müssen.
Deshalb bleibt es bei einer Gesamtkomplexität von O(n²) im worst-case.

EDIT: Naja ok, ich seh grad, dass das doch nicht so einfach war, denn wenn immer was entfernt wird, dann kann ja im nächsten Schritt nicht i+1 innere Schleifendurchläufe sein.

 

[Redfrettchen]

Ok, also nächster Vorschlag:
Es ist doch O(n).
Bei der Speicherkomplexiät erhält man das ja schon. Nun muss nur noch gezeigt werden, dass das bei der Zeitkomplexität nicht mehr ist.
Also wir gehen n mal durch die for-Schleife. Insgesamt werden n Elemente in den Stack eingefügt. Also können auch nur maximal n Elemente gelöscht werden. Im worst-case ist der Stack am Ende leer. Also wurden n Elemente entfernt, man weiß aber nicht genau, wieviele in einem bestimmten Schritt. Aber die Summe aller inneren Schleifendurchläufe über den Durchläufen der äußeren Schleife ist auf jeden Fall n (im worst-case). Also ist die Zeitkomplexität O(n) und die Gesamtkomplexität ebenso.

 

[babuschka]

Hallo Redfrettchen,

vielen Dank für deine kompetente Antworten!! Ich dachte zuerst nämlich auch, dass die Laufzeit n^2 sein muss, wegen den verschachtelten Schleifenaufrufen. Deine Argumentation (letzte Antwort) trifft den Nagel auf den Kopf! 1000 Dank! :toll:

Viele Grüße!
squirrel