Lösen von Rekursionsgleichungen mit zwei Rekursionsaufrufen

15

Ich versuche, eine Θ Grenze für die folgende Wiederholungsgleichung zu finden:

T(n)=2T(n/2)+T(n/3)+2n2+5n+42

Ich denke, der Hauptsatz ist aufgrund der unterschiedlichen Anzahl von Teilproblemen und Unterteilungen ungeeignet. Auch Rekursionsbäume funktionieren nicht, da es kein T(1) bzw. T(0) .

Laura
quelle
5
Wenn Sie eine Wiederholung dieser Form haben, MUSS es einen Basisfall geben, sagen Sie für alle n < 100 . Wenn nicht, gibt es keine Ahnung, wie sich die Wiederholung auswirkt: Vielleicht ist T ( n ) = 2 m für alle n < 100 , wobei m die Größe des ursprünglichen Problems ist! (Stellen Sie sich eine Rekursion vor, bei der Sie die konstante Anzahl der Rekursionen mit allen Teilmengen der ursprünglichen Elemente vergleichen.) Mit anderen Worten: Kein Basisfall impliziert nicht genügend Informationen, um die Rekursion zu lösen. T(n)42n<100T(n)=2mn<100m
Alex ten Brink

Antworten:

15

Ja, Rekursionsbäume funktionieren immer noch! Es spielt keine Rolle, ob der Basisfall bei oder T ( 1 ) oder T ( 2 ) oder sogar T ( 10 100 ) auftritt . Es spielt auch keine Rolle, wie hoch der tatsächliche Wert des Basisfalls ist. Was auch immer dieser Wert ist, es ist eine Konstante.T(0)T(1)T(2)T(10100)

Durch Big-Theta-Brillen gesehen ist die Wiederholung .T(n)=2T(n/2)+T(n/3)+n2

  • Die Wurzel des Rekursionsbaums hat den Wert .n2

  • Die Wurzel hat drei Kinder mit den Werten , ( n / 2 ) 2 und ( n / 3 ) 2 . Somit ist der Gesamtwert aller Kinder ( 11 / 18 ) , n 2 .(n/2)2(n/2)2(n/3)2(11/18)n2

  • Sanity Check: Die Wurzel hat neun Enkelkinder: vier mit Wert , vier mit Wert ( n / 6 ) 2 und eines mit Wert ( n / 9 ) 2 . Die Summe dieser Werte ist ( 11 / 18 ) 2 n 2 .(n/4)2(n/6)2(n/9)2(11/18)2n2

  • Ein einfacher Induktions Nachweis bedeutet , daß für jede ganze Zahl , die 3 l Knoten auf der Stufe l Gesamtwert ( 11 / 18 ) l n 2 .03(11/18)n2

  • Die Niveausummen bilden eine absteigende geometrische Reihe, daher ist nur der größte Term .=0

  • Wir schließen daraus, dass .T(n)=Θ(n2)

JeffE
quelle
14

Sie können die allgemeinere Akra-Bazzi- Methode anwenden .

In Ihrem Fall müssten wir so finden, dassp

12p1+13p=1

(was ergibt )p1.364

und dann haben wir

T(x)=Θ(xp+xp1xt1pdt)=Θ(x2)

Beachten Sie, dass Sie für nicht wirklich lösen müssen . Alles was Sie wissen müssen ist, dass 1 < p < 2 .p1<p<2

Eine einfachere Methode wäre, und zu beweisen, dass g ( x ) begrenzt ist.T(x)=x2g(x)g(x)

Aryabhata
quelle
14

Sei eine Abkürzung für die rechte Seite der Wiederholung. Wir finden eine untere und obere Grenze für f unter Verwendung von T ( n / 3 ) T ( n / 2 ) :f(n)=2T(n/2)+T(n/3)+2n2+5n+42fT(n/3)T(n/2)

3T(n/3)+2n2+5n+42f(n)3T(n/2)+2n2+5n+42

T(n)Θ(n2)T(n)O(n2)Ω(n2)T(n)Θ(n2)


  1. Für einen vollständigen Beweis sollten Sie das beweisen T ist eine zunehmende Funktion.
Raphael
quelle
1
That trick won't work for similar recurrences, like T(n)=2T(n/2)+3T(n/3)+n2, that can be solved with recursion trees. (But even recursion trees won't work for T(n)=2T(n/2)+4T(n/3)+n2, which can be solved with Akra-Bazzi.)
JeffE