Laufzeitbestimmung von rekursiven Algorithmen

[skytale]

Hi! Hab so meine Probleme mit rekursiven Algorithmen. Wie sieht z.B. die Laufzeit von folgender Funktion aus?
Funktion Dummy wird mit n aufgerufen:

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

floor rundet eine Zahl auf eine ganze Zahl ab.
Thx!

[Lukas]

die laufzeit für einen durchlauf ist c1 + (k+1)c2 + kc3 + c4 + c5 = @(k)
k wird mit jedem aufruf halbiert:
k -> k/2 -> k/4 usw.,
z.b. 8=2^3 -> 4=2^2 -> 2=2^1 -> 0
für k=8 sind das sind 4 aufrufe = (ld 8)*k
für k sind es also allgemein @(ld k * k)

[feurio]

wenn dummy mit n aufgerufen wird --->
1: For (i = 1,...,n) { c1*(n+1)
2: l = l+i; c2*n
3: }
4: m = floor(n/2); c4*n*log n
5: if (m > 0) Dummy(m);

c1*(n+1)+c2*n+c4*n*log n=teta (n)

so würde mein vorschlag ausschauen.

lg
azadi

[shabby]

Mein Tipp:
Zeile 2(Laufzeit c2) ist relevant, alles andere Indexrechnung.
1.Aufruf ( 1 * k * c2)
2.Aufruf ( 1/2 * k * c2)
3.Aufruf ( 1/4 * k * c2)
.....
Insgesammt: ((Summe von n=1 bis infinity) 1/n ) * k * c2
Laut Kaiser seinem Papier-Zerreisen-Spiel(Mathe1):
T = 2k * c2 = Theta(k)

Im Allgemeinen sind aber rekursive Algorithmen wirklich blöd (siehe Average Case Analyse von Quicksort !!!)

[feurio]

ahah jetzt checke ich das ganze. m wird wieder zu n oder wie?
so so.

[ded]

@ shabby: Bin auch der Meinung, daß nur Zeile 2 wirklich ins Gewicht fällt.
In deiner Zusammenfassung hat sich IMO aber außer dem offensichtlichen Typo mit Summe 1/n anstatt 1/2 noch ein kleiner Fehler eingeschlichen. Da der Algorithmus nicht bis infinity rechnet, sondern nur bis n, ist T = c2 * k * log2 k = Theta(k log2 k)

THX @ yrucrem. Das Theta fürs c2 ist natürlich k log2 k

[yrucrem]

Intuitiv wuerde ich (wie Lukas) sagen Theta(n * log n).

/edit: Nein, shabby hat vollkommen recht. Es ist Theta(n).

Die Laufzeit fuer einen Durchlauf ist Theta(n) und mit jedem rekursiven aufruf wird das n um die haelfte kleiner, da bietet sich der logarithmus dualis an (bzw. jeder andere logarithmus, die unterscheiden sich ja nur in der basis, verhalten sich aber gleich). Wenn ich mich nicht irre ist bei diesen Algorithmen nicht die genaue Laufzeitformel gefragt, sondern eine Abschaetzung in Theta-Notation.

Auf jeden fall ist z.B.: T = c2 * log2 k NICHT Theta(k) sondern Theta(log2 k) bzw. T = ... + c4*n*log n NICHT Theta(n) sondern Theta(n * log n). Wie kaeme man sonst zu logarithmen mit Laufzeit Theta(n * log n) :-)

[shabby]

Original geschrieben von ded
@ shabby: Bin auch der Meinung, daß nur Zeile 2 wirklich ins Gewicht fällt.
In deiner Zusammenfassung hat sich IMO aber außer dem offensichtlichen Typo mit Summe 1/n anstatt 1/2 noch ein kleiner Fehler eingeschlichen. Da der Algorithmus nicht bis infinity rechnet, sondern nur bis n, ist T = c2 * k * log2 k = Theta(k log2 k)



Ich versteh den Fehler meiner Argumenation nicht ganz.

Für k = 16 z.B.:
c2 * 16, call k = 8
c2 * 8, call k = 4
c2 * 4, call k = 2
c2 * 2, call k = 1
c2 * 1, finished

Also ist die Laufzeit (kleiner wegen floor)

T < k * c2 + k/2 * c2 + k/4 * c2 + k/8 * c2 .....
T <= (2k) * c2 = theta (k)

Wo liegt der Fehler ?

[Lukas]

also ich weiss nicht wie du von
T < k * c2 + k/2 * c2 + k/4 * c2 + k/8 * c2 .....
auf
T <= (2k) * c2 = theta (k)
kommst.
das geht vielleicht bei sume bis unendlich, aber die summe geht wie ded gesagt hat bis k.
bei deinem beispiel für k=16 ist die laufzeit z.b. 16+8+4+2+1=31 -das is zwar ziemlich nah an 2k, aber es is eben nicht 2k.

deswegen kommt man dann glaub ich auf ldk*k = theta(logk*k).

hab aber wie ich versuch hab das für ein paar k zu testen bemerkt dass ich nicht weiss wie man den logarithmus dualis berechnet (mit meinem taschenrechner gehts nicht). weiss wer wie das geht?

[shabby]

Original geschrieben von Lukas
[B]also ich weiss nicht wie du von
T < k * c2 + k/2 * c2 + k/4 * c2 + k/8 * c2 .....
auf
T <= (2k) * c2 = theta (k)
kommst.
das geht vielleicht bei sume bis unendlich, aber die summe geht wie ded gesagt hat bis k.

Das ist eine Reihe aus Mathe 1. (eine bekannte)
Wie du weiters vielleicht siehst hab ich < und nicht = geschrieben, denn weniger Summenelemente -> kleinere Summe.

bei deinem beispiel für k=16 ist die laufzeit z.b. 16+8+4+2+1=31 -das is zwar ziemlich nah an 2k, aber es is eben nicht 2k.

deswegen kommt man dann glaub ich auf ldk*k = theta(logk*k).

Um einmal Aufklärung zu schaffen:
Eine Laufzeit von 2k ist WESENTLICH BESSER als eine Laufzeit von k ld k. (Weil ld k für große k auch groß wird, für 1024 ist es z.B. schon 10).
Zweitens hab ich geschrieben < 2k, von mir aus sags halt O(k) statt theta(k), dass es nicht gegen infinity geht bedeutet ja auch eine BESSERE Laufzeit als 2k.
Zweitens ist es natürlich auch theta(k) weil
k*c2 .... untere Schranke
2*c2 .... obere Schranke
Kernaussage: O(log k * k) ist wesentlich schlechter O(k)


hab aber wie ich versuch hab das für ein paar k zu testen bemerkt dass ich nicht weiss wie man den logarithmus dualis berechnet (mit meinem taschenrechner gehts nicht). weiss wer wie das geht?
Wenn ich mich nicht irre:
log<SUB>a</SUB> x = log x / log a (oder so ähnlich (;))
Falls jemand die Definition vom Logarithmus vergessen haben sollte:
Wenn
a<SUP>y</SUP> = x , dann ist
log<SUB>a</SUB> x = y

[ded]

Um weitere Verwirrung zu vermeiden, habe ich dieses Posting wieder gelöscht. Shabby hat vollkommen recht und ich will niemanden mit meinem Denk- & Bedienfehler nerven.

Sorry für die Platzverschwendung

@ jeuneS2 im darauffolgenden Posting: ja, ich :-) Log[2, 1024] nicht umgekehrt - Aua!

[jeuneS2]

...wenn Mathematica meint, der ld von 1024 (= 2^10) sei 1/10, dann hat irgendjemand Sch***e gebaut.

[shabby]

Original geschrieben von ded


Also ich denke schon, daß n ld n besser also 2n ist. Schau dir das mal in Mathematica an ( Plot[{x*Log [x, 2], 2x}, {x, 1, 20}] ). Mathematica meint übrigens auch, daß der Log von 1024 zur Basis 2 1/10 ist und nicht 10.

Yust my €0.03 (inflation corrected)

M$ betrügt uns alle !
In deren Windows/Zubehör Rechner kommt man nämlich auf
log 1024 = 3.01
ld 1024 = log 1024 / log 2 = 10

Ich sehe eine weltweite Verschwörung ;)