Laufzeitabschätzung

[MrFloppy]

Hallo! Schreib am Fr die Prüfung und sind noch einige Fragen offen.
Ein beliebtes Prüfungsbeispiel ist das Abschätzen von Laufzeiten (Bewerten von kleinen Codestücken). Gibts dafür irgendein Rezept? Ganz vestehe ich das nicht wie ich genau das sehen soll, ob die Laufzeit in n, n² oder n log n ist (oder ähnliches)?

thx for help

[steve]

naja, im prinzip schaust du dir das programm an und überlegst, wie oft eine programmzeile in abhängigkeit von der Anzahl n der Eingabeelemente ausgeführt wird.
wenn sich z.B. bei verdoppelter Anzahl der Elemente die Anzahl der Durchläufe (ist im code meist zeilen- bzw. blockweise zu sehen) verdoppelt, dann hast du Theta(n),
wenn die Durchläufe sich vervierfachen, hast du Theta(n²).
Bei irgendwelchen rekursiven "Teile und Herrsche"-Algorithmen ists meistens Theta(n*logn)

hoff das hilft.

[MrFloppy]

also gibt es da kein allgemeines Rezept wie: for-Schleife -> n², while-Schleife n log n , usw....?

[Irrlicht]

eine while-schleife ist nicht viel anderes als eine for-schleife.
Also: nö.

[eXe]

naja wenns zwei verschachtelte schleifen sind kanns scho mal nimma linear sein - oder? :)

[steve]

nein, mit der art der schleife hats überhaupt nichts zu tun. du musst dir nur übelegen, wie oft eine zeile ausgeführt wird.

Wie eXe schon vermutet hat, deutet eine verschachtelte schleife schon auf nicht-linearität hin. (zum weiteren verwirren: wobei hier in beiden schleifen irgendwie ein n vorkommen muss als bedingung oder so, oder sich zumindest in beiden was verändern muss mit geändertem n, denn sonst ists wieder nur linear )

[MrFloppy]

Laufzeiten in Theta-Notation
--------------------------------------------------------------------

A.)
l = n+10;
while (l>0) {
k = n*n-1;
l = l-1;
}

B.)
while (n>0) {
n=n-1234;
k=n+n*n;
}

C.)
k=n;
while (k>1) {
k=k/2;
l=n*k;
}

D.) Die Funktion Dummy wird mit Argument hn aufgerufen, und ist wie folgt definiert:

Function Dummy(k);
For (i=1,...,k) {
l=l+1;
}
m=floor(K/2);
if (m>0) Dummy(m);

floor rundet auf die nächste ganze Zahl ab.
-------------------------------------------------------------
Für mich ist das Problem, dass ich keine gelösten Sachen dieser Art habe (ausser das Insertion Sort Bsp. ausm Skript), demnach hab ich auch nix zum nachvollziehen, desewegen wärs super, wenn mir hier wär die Lösung zukommen lassen würde.

P.S: Im AlgoDat BUch von "Ottmann, Widmayer" steht zu den Laufzeiten so gut wie gar nix drin. Der Rest unseres Skriptums ist aber 1 zu 1 aus diesem Buch rausgenommen.

[fraka79]

hy mrfloppy

hab hier die lsg.
für deine 4 programmstückchen

hoff sie helfen dir
lg fraka

[MrFloppy]

THX! Genau das hab ich gebraucht. Hilft mir extrem weiter. Danke nochmal!:thumb: :thumb: