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.

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):  $T(n)=2T\left(\lfloor \frac{n}{4}\rfloor \right)+8T\left(\lfloor \frac{n}{16}\rfloor \right)+n$

1.  Vermutung: $T(n)\in O(n\ln (n))⟹T(n)\le c\cdot n\ln (n)$

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

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

4.  Umformen:

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

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

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

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

$\le c\cdot n\ln (n)$  mit  $c\ge \frac{2}{\ln (4)+\ln (16)}=\frac{2}{\ln (64)}$

5.  Induktion:

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

I.V.: $T(n)\le c\cdot n\ln (n)$  für  $n\ge 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):  $T(n)\in O(n\ln (n))$

• Beispiel (2):  $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: $T(n)\in O(n^3{\ln }^2(n))⟹T(n)\le c\cdot n^3{\ln }^2(n)$

2.  Annahme: $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  $t(n)=b\cdot {\ln }^2(2){\left(\frac{n}{2}\right)}^3$  und  $b>0$

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

4.  Umformen:

$=8(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)+n^3\ln (n)$

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

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

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

$=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)$

$=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)$

$=c\cdot n^3{\ln }^2(n)+\begin{array}{c}\underbrace{n^3\ln (n)\cdot (1-c\cdot 2\ln (2))}\\ {}^{\mathrm{c}\mathrm{\ge }\frac{1}{2\ln (2)}}\end{array}+\begin{array}{c}\underbrace{n^3{\ln }^2(2)\cdot (c-b)}\\ {}^{\mathrm{b}\mathrm{\ge }\mathrm{c}}\end{array}$

$\le c\cdot n^3{\ln }^2(n)$  mit  $b\ge c\ge 2{\ln }^{-1}(2)$

5.  Induktion:

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

I.V.: $T(n)\le c\cdot n^3{\ln }^2(n)$  für  $n\ge 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):  $T(n)\in O(n^3{\ln }^2(n))$