Ändern von Variablen in Wiederholungsrelationen

20

Derzeit lerne ich selbst die Einführung in Algorithmen (CLRS) und es gibt eine bestimmte Methode, die in diesem Buch beschrieben wird, um Wiederholungsrelationen zu lösen.

Die folgende Methode kann anhand dieses Beispiels veranschaulicht werden. Angenommen, wir haben die Wiederholung

T(n)=2T(n)+logn

Zunächst nehmen sie die Ersetzung m = lg (n) vor und schließen sie dann wieder an die Wiederholung an und erhalten:

T(2m)=2T(2m2)+m

Bis zu diesem Punkt verstehe ich perfekt. Dieser nächste Schritt ist derjenige, der mich verwirrt.

Sie "benennen" jetzt die Wiederholung und lassen , was anscheinend erzeugtS(m)S(m)=T(2m)

S(m)=2S(m/2)+m

Aus irgendeinem Grund ist mir nicht klar, warum diese Umbenennung funktioniert, und es scheint nur wie Betrug. Kann jemand das besser erklären?

goooser
quelle

Antworten:

15

Es ist sicherlich kein Betrug. Überlegen Sie sich im Kalkül, wie durch Substitution ein schwieriges Integral gelöst werden kann. Die Substitution macht die Gleichung für die Manipulation leichter handhabbar. Außerdem kann die Substitution etwas komplexe Wiederholungen in vertraute verwandeln.

Genau das ist in Ihrem Beispiel passiert. Wir definieren eine neue Wiederholung . Denken Sie daran, dass T ( 2 m ) = 2 T ( 2 m) istS(m)=T(2m). Beachten Sie, dassS(m/2)=T(2mT(2m)=2T(2m2)+m. Wenn dieser spezielle Punkt immer noch unklar ist, seik=m/2und wir bemerken, dass alles, was wir tun, diesesS(k)=T(2k) ist. Nun können wirS(m)ausdrücken,indemwires erweitern auf: S(m)=2S(m/2)+m. Beim Auflösen nachS sehenwir, dass es sich zu unserem vertrauten FreundO(mlogmauflöstS(m/2)=T(2m2)k=m/2S(k)=T(2k)S(m)

S(m)=2S(m/2)+m.
S . Nachdem wir S gelösthaben, wollen wir dies in T ( n ) ausdrücken. Dazu stecken Sie einfach unseren ursprünglichen Wert für m wieder ein und wir haben T O ( log n log log n ) .O(mlogm)ST(n)mTO(lognloglogn)
Nicholas Mancuso
quelle
Richtig, ich verstehe vollkommen, wie Substitution Probleme erleichtert und wie man Werte wieder einfügt, um die Komplexität in Bezug auf n zu erhalten. Ich schätze, meine Frage ist, nachdem man S (m) = T (2 ^ m) gelassen hat, wie man S (m / 2) ableitet. Es ist mir aus irgendeinem Grund einfach nicht klar. Um genauer zu sein, wie schlussfolgern Sie, dass T (2 ^ (m / 2)) = S (m / 2). Es scheint, als ob in der Wiederholung T die Größe des Teilproblems quadratisch ist, während in der Wiederholung S die Größe des Teilproblems halbiert wird
Der einzige Teil, den ich nicht verstehe, ist, wenn Sie sagen: "Beachten Sie, dass S (m / 2) = T (2 ^ (m / 2))". Dies ist der einzige Teil, der für mich nicht offensichtlich ist. Ich bin an die Idee gewöhnt, variable Substitutionen vorzunehmen, aber ich bin nicht wirklich an die Idee gewöhnt, eine vollständige Wiederholung zu ersetzen.
Ah ok, diese letzte Bearbeitung hat es für mich getan. Es ist jetzt klar, danke!
1
Ich habe ein bisschen Zweifel. Wenn ich die Funktion S () schreibe, kmk
erhalte
4

Was bedeutet, ist, dass S und T zwei verschiedene Funktionen sind, die dasselbe Ergebnis liefern, wenn Eingaben als m bzw. 2 m genommen werden.S(m)=T(2m)STm2m

Die Funktion kann als Operator mit zwei internen Schritten betrachtet werden (ansonsten Zusammensetzung der Funktionen):S

  1. Operator: Eingabe: m , Ausgabe: 2 mSm2m

  2. Operator (ursprüngliche Funktion): Eingabe: Ausgabe des ersten Teils, Ausgabe: Wie ursprünglich definiert.T

Deshalb sind dann Übergänge:

m

m2mT(2m)=S(m)
m22m/2T(2m/2)=S(m2).
Vivek Anand Sampath
quelle