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

1. Vermutung:

T (n) \in O (n \ln (n)) ⟹ T (n) \leq c \cdot n \ln (n)

2. Annahme:

T_{s u b 1} (\frac{n}{4}) \leq c \cdot (\frac{n}{4}) \ln (\frac{n}{4})

und

T_{s u b 2} (\frac{n}{16}) \leq c \cdot (\frac{n}{16}) \ln (\frac{n}{16})

3. Substitution:

T (n) \leq 2 \cdot T_{s u b 1} (\frac{n}{4}) + 8 T_{s u b 2} (\frac{n}{16}) + n

4. Umformen:

= 2 (c \cdot (\frac{n}{4}) \ln (\frac{n}{4})) + 8 (c \cdot (\frac{n}{16}) \ln (\frac{n}{16})) + 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

\leq c \cdot n \ln (n)

mit

c \geq \frac{2}{\ln (4) + \ln (16)} = \frac{2}{\ln (64)}

5. Induktion:

I.A.:

n = 2 : T (2) = 2 \leq c \cdot 2 \ln (2) =

mit

c \geq \ln^{- 1} (2) \approx 1,443

I.V.:

T (n) \leq c \cdot n \ln (n)

für

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):

T (n) \in O (n \ln (n))

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

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