Laufzeitbestimmung von rekursiven Algorithmen
Results 1 to 17 of 17
  1. #1

    Title
    Master
    Join Date
    Mar 2002
    Posts
    158
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Laufzeitbestimmung von rekursiven Algorithmen

    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!

  2. #2

    Title
    Hero
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    185
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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)

  3. #3
    feurio's Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    dada-istan
    Posts
    172
    Thanks
    22
    Thanked 23 Times in 14 Posts
    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
    Last edited by feurio; 14-04-2002 at 17:31.

  4. #4
    shabby's Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Location
    Schrödinger, 1040 Wien
    Posts
    267
    Thanks
    2
    Thanked 9 Times in 8 Posts
    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 !!!)

  5. The Following User Says Thank You to shabby For This Useful Post:


  6. #5
    feurio's Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    dada-istan
    Posts
    172
    Thanks
    22
    Thanked 23 Times in 14 Posts
    ahah jetzt checke ich das ganze. m wird wieder zu n oder wie?
    so so.

  7. #6

    Title
    Veteran
    Join Date
    Feb 2002
    Posts
    22
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @ 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
    Last edited by ded; 14-04-2002 at 23:35.
    I'm a pessimist because of intelligence, but an optimist because of will. -- Antonio Gramsci

  8. #7

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    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) :-)
    Last edited by yrucrem; 22-10-2003 at 21:25.

  9. #8
    shabby's Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Location
    Schrödinger, 1040 Wien
    Posts
    267
    Thanks
    2
    Thanked 9 Times in 8 Posts
    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.
    Code:
    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)
    Code:
    T < k * c2 + k/2 * c2 + k/4 * c2 + k/8 * c2 ..... 
    T  <=  (2k) * c2 = theta (k)
    Wo liegt der Fehler ?

  10. #9

    Title
    Hero
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    185
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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?

  11. #10
    shabby's Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Location
    Schrödinger, 1040 Wien
    Posts
    267
    Thanks
    2
    Thanked 9 Times in 8 Posts
    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
    Code:
     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
    Last edited by shabby; 15-04-2002 at 20:06.

  12. #11

    Title
    Veteran
    Join Date
    Feb 2002
    Posts
    22
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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!
    Last edited by ded; 16-04-2002 at 00:28.
    I'm a pessimist because of intelligence, but an optimist because of will. -- Antonio Gramsci

  13. #12
    jeuneS2's Avatar
    Title
    Baccalaureus
    Join Date
    Jan 2002
    Posts
    547
    Thanks
    1
    Thanked 45 Times in 29 Posts
    ...wenn Mathematica meint, der ld von 1024 (= 2^10) sei 1/10, dann hat irgendjemand Sch***e gebaut.
    Why bother spending time reading up on things? Everybody's an authority, in a free land.

  14. #13
    shabby's Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Location
    Schrödinger, 1040 Wien
    Posts
    267
    Thanks
    2
    Thanked 9 Times in 8 Posts
    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

  15. #14
    Bernhard123's Avatar
    Title
    Elite
    Join Date
    Sep 2009
    Location
    Vienna - NÖ
    Posts
    323
    Thanks
    89
    Thanked 24 Times in 16 Posts
    Hallo,
    eine kurze Frage zu Laufzeiten.

    Wenn ich 2 schleifen nacheinander habe, werden meine Laufzeiten Multipliziert (zB.: n*log(n)).
    Jedoch wenn ich zB.: 2 for schleifen habe, wo die äußere log(n) benötigt und die innere zB n^2 -> habe ich dann n^2*logn?

    Multipliziere ich einfach immer meine Laufzeiten der schleife, oder hängt die gesamtlaufzeit nur vom größeren/äußeren/inneren ab?

    Lg

  16. #15

    Title
    Hero
    Join Date
    Dec 2009
    Posts
    212
    Thanks
    15
    Thanked 11 Times in 9 Posts
    Quote Originally Posted by Bernhard123 View Post
    Hallo,
    eine kurze Frage zu Laufzeiten.

    Wenn ich 2 schleifen nacheinander habe, werden meine Laufzeiten Multipliziert (zB.: n*log(n)).
    Jedoch wenn ich zB.: 2 for schleifen habe, wo die äußere log(n) benötigt und die innere zB n^2 -> habe ich dann n^2*logn?

    Multipliziere ich einfach immer meine Laufzeiten der schleife, oder hängt die gesamtlaufzeit nur vom größeren/äußeren/inneren ab?

    Lg
    Wenn du zwei verschachtelte Schleifen hast dann multiplizierst du sie, wenn du zwei Schleifen hintereinander (sprich nicht verschachtelt) hast, dann addierst du sie!

    EDIT: Siehe Post unter mir!
    Last edited by h3r0ld; 26-06-2010 at 20:27.

  17. #16

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    Zuerst muss ich nochmal festhalten, dass Shabby wirklich vollkommen recht hatte ;-) und mein erstes Posting ziemlicher Schwachsinn ist (der Edit ist viel zu mickrig ausgefallen, und der Rest geht voellig an der eigentlichen Fragestellung vorbei).

    Dann moechte ich anmerken, dass man einen acht Jahre alten Thread nur reaktivieren sollte, wenn die eigene Frage zum Thema des Threads passt (hier ging es eigentlich um die Analyse von rekursiven Algorithmen).

    Zum Schluss muss ich sagen, dass die Frage von Bernhard123 nicht so einfach zu beantworten ist [1], und Kochrezepte wie "Zwei verschachtelte Schleifen => Laufzeiten multiplizieren" sehr gefaehrlich sind, weil sie im Allgemeinen nicht gelten. Genaueres dazu findet man im Thread Laufzeitanalyse von Pseudocode.

    [1] Auszer der Teil mit "Zwei Schleifen nacheinander => Multiplizieren", da kann man guten Gewissens, ganz knapp sagen, dass das falsch ist.

  18. #17

    Title
    Hero
    Join Date
    Dec 2009
    Posts
    212
    Thanks
    15
    Thanked 11 Times in 9 Posts
    Vielen Dank yrucrem, ich hätte das beinhart felsenfest behauptet!

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •