imported>Egfgs007: /* Beispiel */ joa, also da wurde die Behauptung, also was zu beweisen war falsch gelesen, was aber keinen inhaltlichen Einfluss hat

2020-05-15T13:46:29Z

Beispiel: joa, also da wurde die Behauptung, also was zu beweisen war falsch gelesen, was aber keinen inhaltlichen Einfluss hat

Neue Seite

Mittels der '''Substitutionsmethode''' für Rekurrenzen lässt sich eine [[Landau-Symbole#Definition|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 [[Landau-Symbole#Definition|Ο-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(1): T(n) ≤ c⋅g(n), mit c > 0 bzw. T(n) ∈ Ο(g(n))  (nach Definition des Ο-Kalküls)
# Annahme(2): Tsub(n/b) ≤ c⋅g(n/b)
# Substitution durch Einsetzen der Annahme in die Rekurrenz: T(n) ≤ a⋅Tsub(n/b) + f(n)  bzw.  T(n) ≤ a⋅(c⋅g(n/b)) + f(n)
# Genaues(3) Umformens zu: T(n) ≤ c⋅g(n)  → Falls dies nicht möglich ist, so war entweder die Vermutung oder die Annahme(2) falsch.
# Beweis von T(n) ≤ c⋅g(n) durch Induktion ⇒ T(n) ∈ Ο(g(n))

{| border="0" cellspacing="0" cellpadding="1"
|valign="top"|(1)  
|Die Vermutung ist die nach oben abgeschätzte Schranke, so dass gilt: T(n) ≤ c⋅g(n) ∈Ο(g(n))
|-
|valign="top"|(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)
|-
|valign="top"|(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)''':  <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>
::<math>\leq c \sdot n \ln(n)</math>  mit  <math>c \geq \frac{2}{\ln(4)+\ln(16)} = \frac{2}{\ln(64)}</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 n0 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 [[Landau-Symbole#Definition|Θ-Kalkül]] im Artikel zum [[Master-Theorem#Verallgemeinerung des zweiten Falls|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) - 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)</math>
::<math>= 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)</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>

::<math>\le c \cdot n^{3}\ln^{2}(n)</math>  mit  <math>\ b \ge c \ge 2\ln^{-1}(2)</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 n0 gezeigt hat, dass T(n) ≤ c⋅n3ln2(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>

[[Kategorie:Komplexitätstheorie]]

Substitutionsmethode - Versionsgeschichte

imported>Egfgs007: /* Beispiel */ joa, also da wurde die Behauptung, also was zu beweisen war falsch gelesen, was aber keinen inhaltlichen Einfluss hat