Ändern von Variablen in Wiederholungsrelationen

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) = 2 T (\sqrt{n}) + \log n

$T(n) = 2T(\sqrt n) + \log n$

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

T (2^{m}) = 2 T (2^{\frac{m}{2}}) + m

$T(2^m) = 2T(2^{\frac{m}{2}}) + 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 erzeugt $S(m)$ $S(m) = T(2^m)$

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

$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?

asymptotics recurrence-relation mathematical-analysis landau-notation goooser
quelle

Antworten:

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 $S(m)=T(2^m)$ . Beachten Sie, dass $T(2^m) = 2T(2^\frac{m}{2}) + m$ . Wenn dieser spezielle Punkt immer noch unklar ist, seiund wir bemerken, dass alles, was wir tun, dieses. Nun können wirausdrücken,indemwires erweitern auf: Beim Auflösen nachwir, dass es sich zu unserem vertrauten Freundauflöst $S(m/2) = T(2^\frac{m}{2})$ $k =m/2$ $S(k) = T(2^k)$ $S(m)$

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

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

S

$S$

. Nachdem wir

gelösthaben, wollen wir dies in

ausdrücken. Dazu stecken Sie einfach unseren ursprünglichen Wert für

und wir haben

O (m \log m)

$O(m \log m)$

S

$S$

T (n)

$T(n)$

m

$m$

T \in O (\log n \log \log n)

$T \in O(\log n \log \log n)$

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!

Ich habe ein bisschen Zweifel. Wenn ich die Funktion S () schreibe, kmk

erhalte

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

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

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

Deshalb sind dann Übergänge:

m \to 2^{m} \to T (2^{m}) = S (m)

$m\to 2^m\to T(2^m) = S(m)$

\frac{m}{2} \to 2^{m / 2} \to T (2^{m / 2}) = S (\frac{m}{2}) .

$\tfrac{m}2\to2^{m/2}\to T(2^{m/2}) = S(\tfrac{m}2)\,.$

Vivek Anand Sampath
quelle