Substitutionsmethode

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

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

[Bearbeiten] 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 Einsetzten 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ätze Schranke, so dass gilt: T(n) ≤ c⋅g(n) ∈Ο(g(n))
⁽²⁾	Falls sich bei 4. T(n) nicht entsprechen genau⁽³⁾ umformen lässt, so darf man von 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).

[Bearbeiten] Beispiel

Beispiel (1): $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: $T(n) \in O(n\ln(n)) \Longrightarrow T(n) \leq c \sdot n\ln(n)$

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

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

4. Umformen:

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

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

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

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

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

5. Induktion:

I.A.: $n = 2: \quad T(2) = 2 \leq c\sdot 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) = 8T \left( \frac{n}{2} \right) + n^{3}ln(n)$

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

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

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

b > 0

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

4. Umformen:

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

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

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

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

$= c \cdot n^{3}\ln^{2}(n) - c \cdot n^{3}2\ln(2)\ln(n) + c \cdot n^{3}\ln^{2}(2) - b \sdot \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 \sdot \ln^{2}(2)n^{3} + c \cdot n^{3}\ln^{2}(2)$

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

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

5. Induktion:

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

I.V.: $T(n) \leq c\cdot n^{3}\ln^{2}(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 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))$