Substitutionsmethode

Mittels der Substitutionsmethode für Rekurrenzen lässt sich eine untere Schranke bzw. obere Schranke des (Rechen-)Aufwandes einer Rekursion bestimmen.

Beschreiben der Methode

Gegeben sei eine Rekursion T(n) der Form T(n) = a⋅T(n/b) + f(n). Um eine obere Schranke zu ermitteln, schätzt man diese zuerst mittels Ο-Kalkül ab. Unter Abschätzen versteht man „geschicktes Raten“. Anschließend wird die Vermutung mit Hilfe von Substitution bewiesen bzw. widerlegt. Analog ist das Vorgehen zur Bestimmung der unteren Schranke.

Vermutung⁽¹⁾: T(n) ≤ c⋅g(n), mit c > 0 bzw. T(n) ∈ Ο(g(n)) (nach Definition des Ο-Kalküls)
Annahme⁽²⁾: T_sub(n/b) ≤ c⋅g(n/b)
Substitution durch Einsetzen der Annahme in die Rekurrenz: T(n) ≤ a⋅T_sub(n/b) + f(n) bzw. T(n) ≤ a⋅(c⋅g(n/b)) + f(n)
Genaues⁽³⁾ Umformens zu: T(n) ≤ c⋅g(n) → Falls dies nicht möglich ist, so war entweder die Vermutung oder die Annahme⁽²⁾ falsch.
Beweis von T(n) ≤ c⋅g(n) durch Induktion ⇒ T(n) ∈ Ο(g(n))

⁽¹⁾	Die Vermutung ist die nach oben abgeschätzte Schranke, so dass gilt: T(n) ≤ c⋅g(n) ∈Ο(g(n))
⁽²⁾	Falls sich bei 4. T(n) nicht entsprechend genau⁽³⁾ umformen lässt, so darf man von der Annahme T_sub(n/b) ≤ c⋅g(n/b) einen Term t(n) niedrigerer Ordnung subtrahieren. Die neue Annahme ist dann: T_sub(n/b) ≤ c⋅g(n/b) – t(n)
⁽³⁾	Hiermit ist gemeint, dass z. B. T(n) ≤ (c+1)⋅g(n) nicht die genaue Form der Vermutung ist. Korrekt wäre beispielsweise T(n) ≤ c⋅g(n) oder auch T(n) ≤ (c-1)⋅g(n).

Beispiel

Beispiel (1): <math>T(n) = 2T \left( \left \lfloor \frac{n}{4} \right \rfloor \right) + 8T \left( \left \lfloor \frac{n}{16} \right \rfloor \right) + n</math>

1. Vermutung: <math>T(n) \in O(n\ln(n)) \Longrightarrow T(n) \leq c \sdot n\ln(n) </math>

2. Annahme: <math>T_{sub1} \left( \frac{n}{4} \right) \leq c \cdot \left( \frac{n}{4} \right) \ln \left( \frac{n}{4} \right)</math> und <math>T_{sub2} \left( \frac{n}{16} \right) \leq c \cdot \left( \frac{n}{16} \right) \ln \left( \frac{n}{16} \right)</math>

3. Substitution: <math> T(n) \leq 2\sdot T_{sub1} \left( \frac{n}{4} \right) + 8T_{sub2} \left( \frac{n}{16} \right) + n</math>

4. Umformen:

<math>= 2 \left( c \cdot \left( \frac{n}{4} \right) \ln \left( \frac{n}{4} \right) \right) + 8 \left( c \cdot \left( \frac{n}{16} \right) \ln \left( \frac{n}{16} \right) \right) + n </math>

<math>= c \sdot \frac{n}{2} \left( \ln(n)-\ln(4) \right) + c \sdot \frac{n}{2} \left( \ln(n)-\ln(16) \right) + n</math>

<math>= c \sdot \frac{n}{2} \left(2\ln(n)-\ln(4)-\ln(16) \right) + n</math>

<math>= c \sdot n \ln(n) - c \sdot \frac{n}{2}\left(\ln(4)+\ln(16) \right) + n</math>

5. Induktion:

I.A.: <math>n = 2: \quad T(2) = 2 \leq c\sdot 2\ln(2) = </math> mit <math>c \geq \ln^{-1}(2) \approx 1{,}443</math>

I.V.: <math>T(n) \leq c\cdot n\ln(n)</math> für <math>n \geq n_0</math>

I.S.: n → n + 1: Da man für ein n₀ gezeigt hat, dass T(n) ≤ c⋅n⋅ln(n) korrekt ist, stimmt die Vermutung. (Es zeigt sich, dass eine Konstante c ≥ 1,443 ausreicht.)

Damit folgt für T(n): <math> T(n) \in O(n\ln(n))</math>

Beispiel (2): <math>T(n) = 8T \left( \frac{n}{2} \right) + n^{3}\ln(n)</math>

Siehe zu demselben Beispiel auch die Aufwandsabschätzung mit dem Θ-Kalkül im Artikel zum Mastertheorem.

1. Vermutung: <math>T(n) \in O \left( n^{3}\ln^2(n) \right) \Longrightarrow T(n) \leq c \sdot n^{3}\ln^2(n)</math>

2. Annahme: <math>T_{sub} \left( \frac{n}{2} \right) = c \sdot \left( \frac{n}{2} \right)^{3} \ln^{2}\left( \frac{n}{2} \right) - t(n) </math> mit <math>t(n) = b\sdot \ln^{2}(2) \left( \frac{n}{2}\right) ^{3} </math> und <math>b > 0</math>

3. Substitution: <math>T(n) \leq 8T_{sub} \left( \frac{n}{2} \right) + n^{3}\ln(n)</math>

4. Umformen:

<math>= 8 \left( c \sdot \left( \frac{n}{2} \right) ^{3} \ln^{2} \left( \frac{n}{2} \right) - b\sdot \ln^{2}(2) \left( \frac{n}{2}\right) ^{3} \right) + n^{3}\ln(n) </math>

<math>= c \cdot n^{3}\ln^{2} \left( \frac{n}{2} \right) - b \sdot \ln^{2}(2)n^{3} + n^{3}\ln(n)</math>

<math>= c \cdot n^{3}\left( \ln(n) - \ln(2) \right) \sdot \left( \ln(n) - \ln(2) \right) - b \sdot \ln^{2}(2) n^{3} + n^{3}\ln(n)</math>

<math>= c \cdot n^{3}\left( \ln^{2}(n) - 2\ln(2)\ln(n) + \ln^{2}(2) \right) - b \sdot \ln^{2}(2) n^{3} + n^{3}\ln(n)</math>

<math>= c \cdot n^{3}\ln^{2}(n) +

\begin{matrix}

 \underbrace{n^{3}\ln(n)\sdot (1- c\cdot2\ln(2))} \\
 {}^{\rm c \ge \frac{1}{2\ln(2)} }\\[-4.5ex]

\end{matrix}

\begin{matrix}

 \underbrace{n^{3}\ln^{2}(2)\cdot (c-b)} \\
 {}^{\rm \ b \ge c}\\[-4.5ex]

\end{matrix} </math>

5. Induktion:

I.A.: <math>n = 2: \quad T(2) \approx 5{,}5 \leq c\sdot 2^{3}\ln^2(2) </math> mit <math>c \geq 1</math>

I.V.: <math>T(n) \leq c\cdot n^{3}\ln^{2}(n)</math> für <math>n \geq n_0</math>

I.S.: n → n + 1: Da man für ein n₀ gezeigt hat, dass T(n) ≤ c⋅n³ln²(n) korrekt ist und c eine beliebig große Konstante sein darf, stimmt die Vermutung. (Eine Konstante c ≥ 4 ist hinreichend groß für alle n.)

Damit folgt für T(n): <math> T(n) \in O(n^{3}\ln^{2}(n))</math>