[Algorithmen] Master-Theorem

Dieses Thema im Forum "Schule, Studium, Ausbildung" wurde erstellt von Smokers, 12. Juli 2010 .

  1. 12. Juli 2010
    Vllt kann mir ja jemand helfen.
    Ich hab echt null plan was ich hier machen soll :


    Aufgabe1: Mastertheorem 2Punkte
    VerwendenSiedieMastermethode,umasymptotischscharfeSchrankenf ¨ urdiefolgendenRekursionsglei-
    chungenzubestimmen.
    a) T(n)=8 · T(n/2 )+ n log n
    b) T(n)=8 · T(n/2 )+4n³
    c) T(n)=8 · T(n/2 )+n^4 · log n
    d) T(n)=8 · T(n/4 )+ n²

    Ich hab ja das Grundgerüst T(n) = a * T(n/b) +f(n)

    also kann ich ablesen das a=8; und das b = 2 bzw einmal 4 ist.
    Was mach ich jetzt damit, ich soll ja damit etwas über die Laufzeit oder die asymptotische Komplexität sagen wenn ich das recht verstanden habe.
    Aber ich hab kein Plan was ich damit machen soll^^

    vllt kann mir hier wer helfen =)

    lg u danke im voraus
     
  2. 13. Juli 2010
    AW: [Algorithmen] Master-Theorem

    mmh helfen kann ich dir leider auch nicht aber es würde mich auch ziemlich ineressieren
     
  3. 13. Juli 2010
    AW: [Algorithmen] Master-Theorem

    Ich denke es inzwischen selbst zu haben.
    Hab erstmal die drei Grundpattern per google gefunden:

    1. WENN f(n) e O(n^(log(a,b) -epsilon)) für beliebiges aber festes epsilon >0 DANN T(n) e TETA (n^(log(a,b)))

    2. WENN f(n) e O(n^(log(a,b))) DANN T(n) e TETA (n^(log(a,b)) * lg(n) )

    3. WENN f(n) e O(n^(log(a,b) +epsilon)) für beliebiges aber festes epsilon >0 und ebenfalls für ein c 0<c<1 und hinreichend großes n DANN gilt
    a) af(n/b)<=cf(n)
    b) T(n) e TETA (n^(log(a,b)))


    Entweder es ist so richtig oder ich machs morgen in der Prüfung falsch...

    also zB bei b)

    T(n)=8 · T(n/2 )+4n³
    a=8;
    b=2;
    f(n)=4n³

    eingesetzt in eine der drei grundpattern die ich per google gefunden habe ergibt das :

    4n³ e TETA(n^(log(8,2)) -> 4n³ e TETA(n³)
    Wenn mich nicht alles täuscht ist das wahr und somit gilt :
    T(n) e TETA(n³ * lg(n) )

    Also sollte die Laufzeit für b) halt n³ * lg(n) sein.
    Keine Ahnung obs so korrekt geschlussfolgert ist, aber naja...
     
  4. 13. Juli 2010
    AW: [Algorithmen] Master-Theorem

    kann dir leider auch nicht helfen, was mich aber interessieren würde, in welchem Zusammenhang machst du solch komplexe (wirken zumindest für einen Laien so) Aufgaben?
     
  5. 13. Juli 2010
    AW: [Algorithmen] Master-Theorem

    laufzeitberechnung rekursiver funktionen.

    hab dunkel in erinnerung dass das bei mir irgendwo im skript steht, ich schau grad mal ob ich was finde.

    /e puh, blicke da leider auch nicht wirklich durch.

    für die aufgabe:
    a = 8
    b = 2
    f(n) = n log n

    komm ich dann zur frage: n log n e O(n²) ?

    setz ich 1 für n ein, stimmt es nicht. was das einem sagen soll - keine ahnung.

    für mich siehts laut Master-Theorem danach aus, dass es nur 3 fälle gibt (quadratisch, kubisch, n mal logarithmisch) und f(n) den gleichen grad haben muss wie n^(log (basis b) a), sonst muss man es anders berechnen.

    naja, genug mit spekulationen, viel glück bei deiner prüfung
     
  6. 13. Juli 2010
    AW: [Algorithmen] Master-Theorem

    Naja Fall 1 und 3 sehen so aus als wenn sie auch für andere Potenzen machbar wären, denn dort gibt es ja epsilon das entweder + oder - genommen wird
    wobei epsilon > 0 sein soll.

    Dementsprechend könnte es ja zB auch sein

    denn bei c)
    würde dann ja sowas stehen = n^4 * n log(n) e TETA (n^(log(a,b) +epsilon))

    gekürzt und eingesetzt steht da also :

    n^4 * n log(n) e TETA (n^(2+epsilon)

    wenn ich jetzt für epsilon 2 nehme, hab ich ja 2+2 = 4 also würde die aussage zutreffen.
    Aber ich weiß ehrlich gesagt nicht ob man das so machen darf oder nicht ^^°

    Aber ka laut wikipedia siehts zumidnest so ähnlich aus

    // siehe dritter Fall wikipedia.... sieht doch okay aus oder?! ^^°
     
  7. 13. Juli 2010
    AW: [Algorithmen] Master-Theorem

    will dich nicht mit meinem rechenweg verwirren... komme da auf ein merkwürdiges ergebnis irgendwie. c müsste 4 sein damit es gleich ist, also 4 * n^4 * log n <= c * n^4 * log n...

    steig da leider absolut nicht durch grad. wär aber cool wenn du irgendwie an ausführliche lösungen kommst, würd mich echt mal interessieren wie man das genau berechnet.
     
  8. Video Script

    Videos zum Themenbereich

    * gefundene Videos auf YouTube, anhand der Überschrift.