#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 + Multi-Zitat Zitieren
#2 13. Juli 2010 AW: [Algorithmen] Master-Theorem mmh helfen kann ich dir leider auch nicht aber es würde mich auch ziemlich ineressieren + Multi-Zitat Zitieren
#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... + Multi-Zitat Zitieren
#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? + Multi-Zitat Zitieren
#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 + Multi-Zitat Zitieren
#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?! ^^° + Multi-Zitat Zitieren
#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. + Multi-Zitat Zitieren