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(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))
(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):
![{\displaystyle T(n)=2T\left(\left\lfloor {\frac {n}{4}}\right\rfloor \right)+8T\left(\left\lfloor {\frac {n}{16}}\right\rfloor \right)+n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d6631b378a58874102621577f293c6821f29a317)
- 1. Vermutung:
![{\displaystyle T(n)\in O(n\ln(n))\Longrightarrow T(n)\leq c\cdot n\ln(n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6911c8cf34206ffac32ecad364c8825aeadde5fd)
- 2. Annahme:
und ![{\displaystyle T_{sub2}\left({\frac {n}{16}}\right)\leq c\cdot \left({\frac {n}{16}}\right)\ln \left({\frac {n}{16}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a5f1da09858577cad4b14586e913d87f4ddaf324)
- 3. Substitution:
![{\displaystyle T(n)\leq 2\cdot T_{sub1}\left({\frac {n}{4}}\right)+8T_{sub2}\left({\frac {n}{16}}\right)+n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cbda1a5466c49156895c1b5a2f60f558bf1a05f3)
- 4. Umformen:
![{\displaystyle =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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ee6853906982453d8653f02b36ed71dd02ef8449)
![{\displaystyle =c\cdot {\frac {n}{2}}\left(\ln(n)-\ln(4)\right)+c\cdot {\frac {n}{2}}\left(\ln(n)-\ln(16)\right)+n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8f34a083a8a4ca427e37d83b84b402c905769f69)
![{\displaystyle =c\cdot {\frac {n}{2}}\left(2\ln(n)-\ln(4)-\ln(16)\right)+n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d48947cb1a13c024119960186c46883997320ffd)
![{\displaystyle =c\cdot n\ln(n)-c\cdot {\frac {n}{2}}\left(\ln(4)+\ln(16)\right)+n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c6792e6ee73cc1f955cf5b64e1b667775fc9214a)
mit ![{\displaystyle c\geq {\frac {2}{\ln(4)+\ln(16)}}={\frac {2}{\ln(64)}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bed811e8e0a2eeecfc4e9d54a4566323752012e6)
- 5. Induktion:
- I.A.:
mit ![{\displaystyle c\geq \ln ^{-1}(2)\approx 1{,}443}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7e4b3e64246ff2e1a96bb9d903167f449ddc0570)
- I.V.:
für ![{\displaystyle n\geq n_{0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fff23d9c13da1b2a7ec6f7fab8fa413b129c6b6c)
- 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):
![{\displaystyle T(n)\in O(n\ln(n))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f9ef19755c4e5050b0e3857eb48a768262a967f2)
- Beispiel (2):
![{\displaystyle T(n)=8T\left({\frac {n}{2}}\right)+n^{3}\ln(n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f1190479e557c06b286e5ad49b4466c6aad0c1e3)
- Siehe zu demselben Beispiel auch die Aufwandsabschätzung mit dem Θ-Kalkül im Artikel zum Mastertheorem.
- 1. Vermutung:
![{\displaystyle T(n)\in O\left(n^{3}\ln ^{2}(n)\right)\Longrightarrow T(n)\leq c\cdot n^{3}\ln ^{2}(n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ad3f4923864d7e5021a1e8b9a1f069bbf79e1919)
- 2. Annahme:
mit
und ![{\displaystyle b>0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/94436473a90bd55191a79c59474cb5456dcbec00)
- 3. Substitution:
![{\displaystyle T(n)\leq 8T_{sub}\left({\frac {n}{2}}\right)+n^{3}\ln(n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8f56f0ce6297cde042e9e5efea56756bdead16df)
- 4. Umformen:
![{\displaystyle =8\left(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}\right)+n^{3}\ln(n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ff9735573f4f9aa90fb36a2697e17dd1364e0b9b)
![{\displaystyle =c\cdot n^{3}\ln ^{2}\left({\frac {n}{2}}\right)-b\cdot \ln ^{2}(2)n^{3}+n^{3}\ln(n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/de4ae642190183f3073673ffb214425eeca21b17)
![{\displaystyle =c\cdot n^{3}\left(\ln(n)-\ln(2)\right)\cdot \left(\ln(n)-\ln(2)\right)-b\cdot \ln ^{2}(2)n^{3}+n^{3}\ln(n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/922e965801e6fe0727a5a3d5410e384d221227bb)
![{\displaystyle =c\cdot n^{3}\left(\ln ^{2}(n)-2\ln(2)\ln(n)+\ln ^{2}(2)\right)-b\cdot \ln ^{2}(2)n^{3}+n^{3}\ln(n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b38d3f81bb7936e1f5d4a7f2a08d9a6d39a01743)
![{\displaystyle =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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e3e899d46436801ba80acccc73e4afb8d4e3df5e)
![{\displaystyle =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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bac1b96cb14a0738d5d8c4971d194a969b2e8a09)
![{\displaystyle =c\cdot n^{3}\ln ^{2}(n)+{\begin{matrix}\underbrace {n^{3}\ln(n)\cdot (1-c\cdot 2\ln(2))} \\{}^{\rm {c\geq {\frac {1}{2\ln(2)}}}}\\[-4.5ex]\end{matrix}}+{\begin{matrix}\underbrace {n^{3}\ln ^{2}(2)\cdot (c-b)} \\{}^{\rm {\ b\geq c}}\\[-4.5ex]\end{matrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/29ad026842fa988c76bfc70d35824a280f09a08d)
mit ![{\displaystyle \ b\geq c\geq 2\ln ^{-1}(2)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/deb222775ec143e04e5738e09e69b97092caf6bb)
- 5. Induktion:
- I.A.:
mit ![{\displaystyle c\geq 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b572227b88516d6f52906d3dc41c900677ee22da)
- I.V.:
für ![{\displaystyle n\geq n_{0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fff23d9c13da1b2a7ec6f7fab8fa413b129c6b6c)
- 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):
![{\displaystyle T(n)\in O(n^{3}\ln ^{2}(n))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/87c02ee05197efe68d5b4d17ffa29a6fb16fb0e3)