Verständnis Master-Theorem

Question

Allgemeinform: T(n) = aT(n/b) + f(n)

Also muss ich vergleichen n^logb (a) mit f (n)

wenn n^logba>f(n)Fall 1 und T(n)=Θ(n^logb(a))

wenn n^logba < f(n) ist Fall 2 und T(n)=Θ((n^logb(a))(logb(a)))

Stimmt das? Oder habe ich etwas falsch verstanden?

Und was ist mit Fall 3? Wann ist es anzuwenden?

Answer 1

Ich denke, Sie haben es falsch verstanden. wenn n^logba> f (n) ist Fall 1 und T (n) = Θ (n^logb (a))

Hier sollten Sie nicht etwa f besorgt sein (n) als Ergebnis Sie bekommen ist T (n) = Θ (n^logb (a)). f (n) ist ein Teil von T (n) ..und wenn Sie das Ergebnis T (n) erhalten, wird dieser Wert inklusive f (n) sein. Also, es gibt keine Notwendigkeit, diesen Teil zu berücksichtigen.

Lassen Sie mich wissen, wenn Sie nicht klar sind.

Answer 2

Hinweis: Ich verstehe, dass dies zu spät ist, um diese Frage zu beantworten. Ich stelle es gerade hier für die zukünftigen Generationen :)

Meister Theorem zur Lösung Rezidive

Rezidive in einer Division auftreten und erobert Strategie, komplexe Probleme zu lösen.

Was löst es?

• Es löst die Wiederholungen der Form T (n) = aT (n/b) + f (n).
• Ein sollte größer oder gleich 1 sein. Das bedeutet, dass das Problem zumindest einmal auf ein kleineres Unterproblem reduziert wird. Mindestens eine Rekursion wird benötigt
• b sollte größer als 1 sein. Das bedeutet, dass bei jeder Rekursion die Größe des Problems auf eine kleinere Größe reduziert wird. Wenn b nicht größer als 1 ist, bedeutet dies, dass unsere Teilprobleme nicht kleiner sind.
• f (n) muss für relativ größere Werte von n positiv sein.

Betrachten Sie das Bild unten:

Lets sagen, dass wir ein Problem der Größe n gelöst werden müssen. Bei jedem Schritt kann das Problem in Teilprobleme unterteilt werden, und jedes Teilproblem ist kleiner, wobei die Größe um einen Faktor b verringert wird.

Die obige Aussage in einfachen Worten bedeutet, dass ein Problem der Größe n in ein Unterproblem von relativ kleiner Größe n/b unterteilt werden kann.

Auch das obige Diagramm zeigt, dass am Ende, wenn wir die Probleme mehrere Male geteilt haben, jedes Teilproblem so klein sein würde, dass es in konstanter Zeit gelöst werden kann.

Für die unter Ableitung betrachten log an der Basis b

Lassen Sie uns sagen, dass H die Höhe des Baumes ist, dann H = logn. Anzahl der Blätter = a^logn.

• Gesamtarbeit auf Stufe 1 durchgeführt: f (n)
• Gesamt auf Stufe geleistete Arbeit 2: a * f (n/b)
• Gesamt auf Stufe geleistete Arbeit 1: a * a * f (n/b2)
• Gesamtarbeit zuletzt erledigt Stufe: Anzahl der Blätter * θ (1). Dies entspricht n^loga

Drei Fälle von Master-Theorem

Fall 1: Nehmen wir nun an, dass die Kosten für die Operation auf jeder Ebene um einen signifikanten Faktor erhöht und die Wenn wir die Blattebene erreichen, wird der Wert von f (n) polynomiell kleiner als der Wert n^loga. Dann wird die Gesamtlaufzeit stark von den Kosten des letzten Levels dominiert. Daher T (n) = θ (n^loga)

Fall 2: Nehmen wir an, dass die Kosten für den Betrieb auf jeder Ebene in etwa gleich sind. In diesem Fall ist f (n) ungefähr gleich n^loga. Daher wäre die Gesamtlaufzeit f (n) mal die Gesamtanzahl der Stufen. T (n) = θ (n^loga * logn) wobei k> = 0 sein kann. Wo logn die Höhe eines Baumes für k wäre> = 0

Fall 3: Nehmen wir an, dass die Kosten für den Betrieb auf jeder Ebene wird auf jeder Ebene um einen signifikanten Faktor verringert und durch die Zeit, die wir Erreichen Sie die Blattebene, wird der Wert von f (n) polynomiell größer als der Wert n^loga. Dann wird die Gesamtlaufzeit stark von den Kosten der ersten Stufe dominiert. Also T (n) = θ (f (n))

Wenn Sie sich für ein genaueres Lesen und vielleicht ein paar Beispiele zum Üben interessieren. Sie können immer meinen Blog-Eintrag für das gleiche besuchen. Master Method to Solve Recurrences