Substitutionsmethode

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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

Beschreiben der Methode

[Bearbeiten | Quelltext bearbeiten]

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(1): T(n) ≤ c⋅g(n), mit c > 0 bzw. T(n) ∈ Ο(g(n))  (nach Definition des Ο-Kalküls)
  2. Annahme(2): Tsub(n/b) ≤ c⋅g(n/b)
  3. 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)
  4. 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.
  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 (1):  
1.  Vermutung:
2.  Annahme:   und  
3.  Substitution:
4.  Umformen:
  mit  
5.  Induktion:
I.A.:   mit  
I.V.:   für  
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):  
  • Beispiel (2):  
Siehe zu demselben Beispiel auch die Aufwandsabschätzung mit dem Θ-Kalkül im Artikel zum Mastertheorem.
1.  Vermutung:
2.  Annahme:   mit    und  
3.  Substitution:
4.  Umformen:
  mit  
5.  Induktion:
I.A.:   mit  
I.V.:   für  
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):