Substitutionsmethode

Mittels d​er Substitutionsmethode für Rekurrenzen lässt s​ich eine untere Schranke bzw. o​bere Schranke d​es (Rechen-)Aufwandes e​iner 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.

1. Vermutung⁽¹⁾: T(n) ≤ c⋅g(n), mit c > 0 bzw. T(n) ∈ Ο(g(n))  (nach Definition des Ο-Kalküls)
2. Annahme⁽²⁾: T_sub(n/b) ≤ c⋅g(n/b)
3. 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)
4. Genaues⁽³⁾ Umformens zu: T(n) ≤ c⋅g(n)  → Falls dies nicht möglich ist, so war entweder die Vermutung oder die Annahme⁽²⁾ falsch.
5. Beweis von T(n) ≤ c⋅g(n) durch Induktion ⇒ T(n) ∈ Ο(g(n))

^(1)	Die Vermutung ist die nach oben abgeschätzte Schranke, so dass gilt: T(n) ≤ c⋅g(n) ∈Ο(g(n))
^(2)	Falls sich bei 4. T(n) nicht entsprechend genau^(3) umformen lässt, so darf man von der Annahme Tsub(n/b) ≤ c⋅g(n/b) einen Term t(n) niedrigerer Ordnung subtrahieren. Die neue Annahme ist dann: Tsub(n/b) ≤ c⋅g(n/b) – t(n)
^(3)	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):  ${\displaystyle T(n)=2T\left(\left\lfloor {\frac {n}{4}}\right\rfloor \right)+8T\left(\left\lfloor {\frac {n}{16}}\right\rfloor \right)+n}$

1.  Vermutung: ${\displaystyle T(n)\in O(n\ln(n))\Longrightarrow T(n)\leq c\cdot n\ln(n)}$

2.  Annahme: ${\displaystyle T_{sub1}\left({\frac {n}{4}}\right)\leq c\cdot \left({\frac {n}{4}}\right)\ln \left({\frac {n}{4}}\right)}$  und  ${\displaystyle T_{sub2}\left({\frac {n}{16}}\right)\leq c\cdot \left({\frac {n}{16}}\right)\ln \left({\frac {n}{16}}\right)}$

3.  Substitution: ${\displaystyle T(n)\leq 2\cdot T_{sub1}\left({\frac {n}{4}}\right)+8T_{sub2}\left({\frac {n}{16}}\right)+n}$

4.  Umformen:

${\displaystyle =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}$

${\displaystyle =c\cdot {\frac {n}{2}}\left(\ln(n)-\ln(4)\right)+c\cdot {\frac {n}{2}}\left(\ln(n)-\ln(16)\right)+n}$

${\displaystyle =c\cdot {\frac {n}{2}}\left(2\ln(n)-\ln(4)-\ln(16)\right)+n}$

${\displaystyle =c\cdot n\ln(n)-c\cdot {\frac {n}{2}}\left(\ln(4)+\ln(16)\right)+n}$

${\displaystyle \leq c\cdot n\ln(n)}$  mit  ${\displaystyle c\geq {\frac {2}{\ln(4)+\ln(16)}}={\frac {2}{\ln(64)}}}$

5.  Induktion:

I.A.: ${\displaystyle n=2:\quad T(2)=2\leq c\cdot 2\ln(2)=}$  mit  ${\displaystyle c\geq \ln ^{-1}(2)\approx 1{,}443}$

I.V.: ${\displaystyle T(n)\leq c\cdot n\ln(n)}$  für  ${\displaystyle n\geq n_{0}}$

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):  ${\displaystyle T(n)\in O(n\ln(n))}$

• Beispiel (2):  ${\displaystyle T(n)=8T\left({\frac {n}{2}}\right)+n^{3}\ln(n)}$

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

1.  Vermutung: ${\displaystyle T(n)\in O\left(n^{3}\ln ^{2}(n)\right)\Longrightarrow T(n)\leq c\cdot n^{3}\ln ^{2}(n)}$

2.  Annahme: ${\displaystyle T_{sub}\left({\frac {n}{2}}\right)=c\cdot \left({\frac {n}{2}}\right)^{3}\ln ^{2}\left({\frac {n}{2}}\right)-t(n)}$  mit  ${\displaystyle t(n)=b\cdot \ln ^{2}(2)\left({\frac {n}{2}}\right)^{3}}$  und  ${\displaystyle b>0}$

3.  Substitution: ${\displaystyle T(n)\leq 8T_{sub}\left({\frac {n}{2}}\right)+n^{3}\ln(n)}$

4.  Umformen:

${\displaystyle =8\left(c\cdot \left({\frac {n}{2}}\right)^{3}\ln ^{2}\left({\frac {n}{2}}\right)-b\cdot \ln ^{2}(2)\left({\frac {n}{2}}\right)^{3}\right)+n^{3}\ln(n)}$

${\displaystyle =c\cdot n^{3}\ln ^{2}\left({\frac {n}{2}}\right)-b\cdot \ln ^{2}(2)n^{3}+n^{3}\ln(n)}$

${\displaystyle =c\cdot n^{3}\left(\ln(n)-\ln(2)\right)\cdot \left(\ln(n)-\ln(2)\right)-b\cdot \ln ^{2}(2)n^{3}+n^{3}\ln(n)}$

${\displaystyle =c\cdot n^{3}\left(\ln ^{2}(n)-2\ln(2)\ln(n)+\ln ^{2}(2)\right)-b\cdot \ln ^{2}(2)n^{3}+n^{3}\ln(n)}$

${\displaystyle =c\cdot n^{3}\ln ^{2}(n)-c\cdot n^{3}2\ln(2)\ln(n)+c\cdot n^{3}\ln ^{2}(2)-b\cdot \ln ^{2}(2)n^{3}+n^{3}\ln(n)}$

${\displaystyle =c\cdot n^{3}\ln ^{2}(n)-c\cdot n^{3}2\ln(2)\ln(n)+n^{3}\ln(n)-b\cdot \ln ^{2}(2)n^{3}+c\cdot n^{3}\ln ^{2}(2)}$

${\displaystyle =c\cdot n^{3}\ln ^{2}(n)+{\begin{matrix}\underbrace {n^{3}\ln(n)\cdot (1-c\cdot 2\ln(2))} \\{}^{\rm {c\geq {\frac {1}{2\ln(2)}}}}\\[-4.5ex]\end{matrix}}+{\begin{matrix}\underbrace {n^{3}\ln ^{2}(2)\cdot (c-b)} \\{}^{\rm {\ b\geq c}}\\[-4.5ex]\end{matrix}}}$

${\displaystyle \leq c\cdot n^{3}\ln ^{2}(n)}$  mit  ${\displaystyle \ b\geq c\geq 2\ln ^{-1}(2)}$

5.  Induktion:

I.A.: ${\displaystyle n=2:\quad T(2)\approx 5{,}5\leq c\cdot 2^{3}\ln ^{2}(2)}$  mit  ${\displaystyle c\geq 1}$

I.V.: ${\displaystyle T(n)\leq c\cdot n^{3}\ln ^{2}(n)}$  für  ${\displaystyle n\geq n_{0}}$

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):  ${\displaystyle T(n)\in O(n^{3}\ln ^{2}(n))}$