Wie verwende ich Master-Theorem, um Rekursion zu beschreiben?

Question

Vor kurzem habe ich Rekursion studiert; wie man es schreibt, analysiert, usw. Ich habe für eine Weile gedacht, dass Wiederholung und Rekursion die gleiche Sache sind, aber einige Probleme bei den letzten Hausaufgaben und Quizfragen lassen mich denken, dass es kleine Unterschiede gibt, dass "Wiederholung" der Weg ist beschreiben ein rekursives Programm oder eine rekursive Funktion.

Das war mir bis vor kurzem sehr griechisch, als mir klar wurde, dass es etwas gibt, das als "Hauptsatz" bezeichnet wird, um die "Wiederholung" für Probleme oder Programme zu schreiben. Ich habe die Wikipedia-Seite durchgelesen, aber wie üblich sind die Dinge so formuliert, dass ich nicht wirklich verstehe, worüber sie spricht. Ich lerne viel besser mit Beispielen.

Also, ein paar Fragen: Lassen Sie uns sagen Sie diese Wiederholung gegeben:

r (n) = 2 * r (n-2) + r (n-1);
R (1) = r (2) = 1

Ist dies in der Tat in der Form des Master-Theorems? Wenn ja, in Worten, was sagt es? Wenn Sie versuchen würden, ein kleines Programm oder einen Baum der Rekursion basierend auf dieser Wiederholung zu schreiben, wie würde das aussehen? Sollte ich einfach versuchen, Zahlen zu ersetzen, ein Muster zu sehen, dann einen Pseudocode zu schreiben, der rekursiv dieses Muster erzeugen könnte, oder, da dies in Form des Hauptsatzes sein mag, gibt es einen einfacheren mathematischen Ansatz?

Nehmen wir an, Sie wurden gebeten, die Wiederholung T (n) für die Anzahl der Ergänzungen zu finden, die von dem aus der vorherigen Wiederholung erstellten Programm ausgeführt wurden. Ich kann sehen, dass der Basisfall wahrscheinlich T (1) = T (2) = 0 wäre, aber ich bin mir nicht sicher, wohin ich von dort aus gehen soll.

Grundsätzlich frage ich, wie man von einer gegebenen Wiederholung zu Code und umgekehrt geht. Da dies nach dem Hauptsatz aussieht, frage ich mich, ob es eine geradlinige und mathematische Methode gibt, dies zu tun.

EDIT: Okay, ich habe einige meiner früheren Aufgaben durchgesehen, um ein anderes Beispiel zu finden, wo ich gefragt werde, 'die Wiederholung zu finden', was der Teil dieser Frage ist mit.

Rezidive, die in der besten Art und Weise die Anzahl der Additionsoperationen im folgende Programmfragment beschreibt (wenn sie mit l == 1 und R genannt == n)

int example(A, int l, int r) { 
    if (l == r) 
    return 2; 
    return (A[l] + example(A, l+1, r); 
} 

Answer 1

Vor ein paar Jahren bewiesen Mohamad Akra und Louay Bazzi ein Ergebnis, das die Master-Methode verallgemeinert - es ist fast immer besser. Sie sollten wirklich nicht das Master-Theorem verwenden mehr ...

Siehe zum Beispiel dieser Zuschreibung: http://courses.csail.mit.edu/6.046/spring04/handouts/akrabazzi.pdf

Grundsätzlich erhalten Sie Ihre Wiederholung 1 in dem Papier wie Gleichung zu sehen, die Koeffizienten pflückt, und integrieren Sie den Ausdruck in Satz 1.

Answer 2

Ihrer Methode, geschrieben in Code mit einer rekursiven Funktion, würde so aussehen:

function r(int n) 
{ 
    if (n == 2) return 1; 
    if (n == 1) return 1; 
    return 2 * r(n-2) + r(n-1); // I guess we're assuming n > 2 
} 

Ich bin nicht su Was "Wiederholung" ist, sondern eine rekursive Funktion ist einfach eine, die sich selbst nennt.

rekursive Funktionen benötigen eine Escape-Klausel (einig nicht-rekursiven Fall - beispielsweise „wenn n == 1 return 1“) einen Stapelüberlauf Fehler zu verhindern (d.h.so viel, wird die Funktion aufgerufen, dass der Dolmetscher aus dem Speicher oder anderen Ressourcen läuft)

Answer 3

Ein einfaches Programm, das das würde aussehen implementieren würde wie:

public int r(int input) { 
    if (input == 1 || input == 2) { 
     return 1; 
    } else { 
     return 2 * r(input - 2) + r(input -1) 
    } 
} 

Sie würden auch sicher, dass die Eingabe vornehmen müssen wird keine unendliche Rekursion verursachen, zum Beispiel wenn die Eingabe am Anfang kleiner als 1 war. Wenn dies kein gültiger Fall ist, dann gebe einen Fehler zurück, falls er gültig ist, und gebe den entsprechenden Wert zurück.

Answer 4

„ich bin nicht ganz sicher, was‚Wiederholung‘ist entweder“

die Definition eines „Rekursion“ ist eine Folge von Zahlen „, deren Domäne ist etwas unendlich von ganzen Zahlen und deren Reichweite ist eine Reihe von reellen Zahlen. " Mit der zusätzlichen Bedingung, dass die Funktion, die diese Sequenz beschreibt, "ein Mitglied der Sequenz in Bezug auf eine vorherige Sequenz definiert".

Und das Ziel dahinter ist meiner Meinung nach, von einer rekursiven Definition zu einer anderen zu gelangen. Angenommen, Sie hätten T (0) = 2 und T (n) = 2 + T (n-1) für alle n> 0, müssten Sie vom Ausdruck "T (n) = 2 + T (n -1) "zu einem wie" 2n + 2 ".

Quellen: 1) "Diskrete Mathematik mit Graphentheorie - Second Edition" von Edgar G. Goodair und Michael M. Parmenter 2) "Computeralgorithmen C++" von Ellis Horowitz, Sartaj Sahni und Sanguthevar Rajasekaran.

Answer 5

Zachary:

Können sagen Sie diese Rezidiv gegeben:

r (n) = 2 * r (n-2) + r (n-1); r (1) = r (2) = 1

Ist dies in der Tat in der Form der Hauptsatz? Wenn ja, in Worten, was sagt es? ?

Ich denke, dass Ihr Rekursion was sagt, ist, dass für die Funktion von „r“ mit „n“ als Parameter (die Gesamtzahl der Daten, welche Sets Sie Eingabe), was auch immer Sie bei den n-ten bekommen Die Position des Datensatzes ist die Ausgabe der n-1-ten Position plus zweimal, was auch immer das Ergebnis der n-2-ten Position ist, wobei keine nichtrekursive Arbeit ausgeführt wird. Wenn Sie versuchen, eine Rekursionsbeziehung zu lösen, versuchen Sie, sie so auszudrücken, dass sie keine Rekursion erfordert.

Allerdings glaube ich nicht, dass das in der richtigen Form für die Master Theorem-Methode ist. Ihre Aussage ist eine "lineare Rekursionsbeziehung zweiter Ordnung mit konstanten Koeffizienten". Nach meinem alten Discrete Math Lehrbuch ist das die Form, die Sie haben müssen, um die Wiederholungsbeziehung zu lösen.

Hier ist die Form, die sie geben:

r(n) = a*r(n-1) + b*r(n-2) + f(n) 

für 'a' und 'b' sind einige Konstanten und f (n) ist eine Funktion von n. In Ihrer Aussage ist a = 1, b = 2 und f (n) = 0. Wann immer f (n) gleich Null ist, wird die Rekursionsbeziehung als "homogen" bezeichnet. Dein Ausdruck ist also homogen.

Ich glaube nicht, dass Sie eine homogene Rekursion Relation mit der Master-Methode Theoerm lösen können, weil f (n) = 0. Keines der Fälle für Master Method Theorem erlauben, dass, weil n-zu-der-Power- von irgendetwas kann nicht gleich Null sein. Ich könnte mich irren, weil ich nicht wirklich ein Experte darin bin, aber ich kann nicht, dass es möglich ist, eine homogene Wiederholungsbeziehung mit der Meistermethode zu lösen.

ich, dass die Art und Weise eine homogene Rekursion zu lösen um 5 Schritte zu gehen:

1) bilden die charakteristische Gleichung, die etwas von der Form: Wenn Sie

x^k - c[1]*x^k-1 - c[2]*x^k-2 - ... - c[k-1]*x - c[k] = 0 

hab bekam nur 2 rekursive Instanzen in Ihrer homogenen Rekursion dann nur Sie Ihre Gleichung in die quadratische Gleichung ändern müssen, wo

x^2 - a*x - b = 0 

Diese bec ist aus eine Rekursion der Form von

r(n) = a*r(n-1) + b*r(n-2) 

Kann als

r(n) - a*r(n-1) - b*r(n-2) = 0 

2) Nach der Rekursion als charakteristische Gleichung neu geschrieben wird neu geschrieben werden, als nächstes die Wurzeln findet (x [1] und x [2]) der charakteristischen Gleichung.

3) Mit Ihren Wurzeln, wird Ihre Lösung nun eine der beiden Formen annehmen:

if x[1]!=x[2] 
    c[1]*x[1]^n + c[2]*x[2]^n 
else 
    c[1]*x[1]^n + n*c[2]*x[2]^n 

für n> 2. 4) Mit der neuen Form Ihrer rekursive Lösung verwenden Sie die Anfangsbedingungen (r (1) und r (2)) c finden [1] und c [2]

gehen hier mit Ihrem Beispiel ist was wir bekommen:

1) r (n) = 1 * r (n-1) + 2 * r (n-2) => x^2 - x - 2 = 0

2) Lösung für x

x = (-1 +- sqrt(-1^2 - 4(1)(-2)))/2(1) 

    x[1] = ((-1 + 3)/2) = 1 
    x[2] = ((-1 - 3)/2) = -2 

3) Da x [1]! = X [2], Ihre Lösung auf die Form: Jetzt

c[1](x[1])^n + c[2](x[2])^n 

4) Verwenden Sie Ihre Anfangsbedingungen die beiden Konstanten c zu finden [1] und c [2]:

c[1](1)^1 + c[2](-2)^1 = 1 
c[1](1)^2 + c[2](-2)^2 = 1 

Ehrlich gesagt, ich bin nicht sicher, was Deine Konstanten sind in dieser Situation, ich habe an dieser Stelle angehalten. Ich schätze, du musst Zahlen einstecken, bis du irgendwie einen Wert für c [1] und c [2] bekommen hast, der beide diese beiden Ausdrücke erfüllen würde.Entweder die oder Zeilenreduktion auf einer Matrix C durchzuführen, wobei C gleich:

[ 1 1 | 1 ] 
[ 1 2 | 1 ] 

Zachary:

Rezidive, die die Anzahl der Additionsoperationen im folgende Programmfragment im besten Weise beschreibt (wenn sie mit L == == 1 und R n)

int example(A, int l, int r) { 
    if (l == r) 
    return 2; 
    return (A[l] + example(A, l+1, r); 
} 

hier genannt ‚S die Zeitkomplexitätswerte für Ihren gegebenen Code für, wenn r> l:

int example(A, int l, int r) {  => T(r) = 0 
    if (l == r)    => T(r) = 1 
    return 2;    => T(r) = 1 
    return (A[l] + example(A, l+1, r); => T(r) = 1 + T(r-(l+1)) 
} 

Total:      T(r) = 3 + T(r-(l+1)) 

Else, wenn r == l dann T (r) = 2, weil die if-Anweisung und die Rückkehr erfordern beide 1 Schritt pro Ausführung.