Eine Technik zur Vereinfachung von aus Rekursionsgleichungen entstandenen Wachstumsklassen

Kannst du die asymptotische Wachstumsklassen der Folgen ausrechnen, die durch die folgenden Rekursionsgleichungen definiert sind? $$\begin{align*}T(n) &= T(n - \sqrt{n}) + \tfrac{1}{\sqrt{n}} \\ T(n) &= T(n - \sqrt{n}) + \sqrt{\tfrac{\log n}{n}} \\ T(n) &= T(n-\log^2 n) + \tfrac{1}{n} \\ T(n) &= T(n ~ / ~ 2) + \tfrac{1}{\log n} \\ T(n) &= T(n ~ / ~ 2) + e^{\sqrt{\log n}} \\ T(n) &= 2 ~ T(n ~ / ~ 2) + \tfrac{n\log\log n}{\log n}\end{align*}$$

In einem späteren Entwurf meiner Bachelorthese, die hauptsächlich um die grundsätzliche Eigenschaften der asymptotischen Wachstumsklassen und die Partialsummen ging, habe ich mich ein bisschen in die Rekursionsgleichungen vertieft. Leider war dieser Abschnitt der These nicht ausführlich genug entwickelt, um im entgültigen Entwurf gehalten zu sein. Aber drin gab es eine tolle Lösungstechnik, die mindestens einen Blogeintrag verdient!

Ein Schlüsselbegriff, der innerhalb meiner These entwickelt wird, ist die Mäßigkeit der Wachstumsklassen. Meiner Definition nach, die Wachstumsklasse von einer Folge $(a_n)$ ist mäßig, wenn $$(b_n)\in\Theta(n) ~ \implies ~ a_{b_n} = \Theta(a_n)$$ d.h., wenn man $(a_n)$ durch einer Folge $(b_n)$, die der linealen Wachstumsklasse entspricht, neu indiziert, ist seine Wachstumsklasse nicht geändert. Diese Eigenschaft hängt nur von der Wachstumsklasse von $(a_n)$ ab, also, wenn $a_n = \Theta(a'_n)$ und $(a_n')$ mäßig ist, dann muss $(a_n)$ auch mäßig sein. Viele häufige Wachstumsklassen zeigen diese Eigenschaft (z.B. polynomiales Wachstum, logarithmisches Wachstum, alle seine Summen, Produkte und Wurzeln, usw) und es hat zur Folge viele andere günstige Eigenschaften.

Unter ihnen ist eine einfache aber sehr wichtige Eigenschaft, die sich uns als sehr nützlich zur Lösung der Rekursionsgleichungen beweisen wird. Es heißt: wenn $(a_n)$ mäßig ist und $b_n = \mathcal O(n)$, dann kann mann folgern, dass $$\sum_{k=n}^{n + b_n} a_n = \Theta(a_n b_n)$$ Diese Schlussfolgerung lässt sich ganz einfach beweisen und von selbst nicht so bahnbrechend, aber wir werden gleich sehen, wie es zur Trivialisierung einiger Rekursionsgleichungen führt.

Überleg mal die folgende Rekursionsgleichung: $$T(n) = T(n - a_n) + b_n$$ wo $T(0) > 0$ und $(a_n)$ eine Folge von natürlichen Zahlen ist, derart, dass $a_n < n$ für alle $n\in\mathbb N$ (damit $T(n-a_n)$ wohldefiniert ist). Unter bestimmten Bedingungen kann man beweisen, dass die Wachstumsklasse von $T$ nur von den respektiven Wachstumsklassen von $(a_n)$ und $(b_n)$ ist. Diese Unabhängigkeit von der bestimmten Folgen hat zur Folge, dass mann $(a_n)$ oder $(b_n)$ willkürlich durch günstiger Folgen ersetzen kann, die aus der gleichen Wachstumsklassen gezogen sind, um die Berechnung der Wachstumsklasse von $T$ zu erleichtern. Und wenn $(a_n)$ und $(b_n)$ mäßig sind, dann (so die Eigenschaft der mäßigen Wachstumsklassen, auf die wir hingewiesen haben) trifft zu: $$b_n = \Theta\bigg(\sum_{k=n-a_n+1}^n \frac{b_k}{a_k}\bigg)$$ damit die durch der folgenden Rekursionsgleichung definierten Funktion $T^\ast$ der gleichen Wachstumsklasse als $T$ entspricht: $$T^\ast(n) = T^\ast (n - a_n) + \sum_{k=n-a_n + 1}^n \frac{b_k}{a_k}$$ Aber es ist ganz einfach zu beweisen, dass die folgende Definition für $T^\ast$ diese Rekursionsgleichung bestätigt: $$T^\ast(n) = \sum_{k=0}^n \frac{b_k}{a_k}$$ und deshalb: $$T(n) = \Theta\bigg(\sum_{k=0}^n \frac{b_k}{a_k}\bigg)$$ Diese Technik reduziert die Berechnung der Wachstumsklasse von $T$ auf die Berechnung der Wachtumsklasse dieser Partialsumme, und in meiner These habe ich wohl ausführlich viele Technik zur Berechnung der Wachtumsklasse von Partialsummen entwickelt. Kurz gefasst wissen wir, dass solange $(a_n)$ und $(b_n)$ bestimmte ziemlich einfache Bedingungen erfüllen:

$$T(n) = T(n - a_n) + b_n ~ \implies ~ T(n) = \Theta\bigg(\sum_{k=1}^{a_n} \frac{b_k}{a_k}\bigg)$$

Zum Beispiel:

$$\begin{align*}T(n) = T(n - \sqrt{n}) + \frac{1}{\sqrt{n}} ~ &\implies ~ T(n) = \Theta(\log n) \\ T(n) = T(n - \sqrt{n}) + \sqrt{\frac{\log n}{n}} ~ &\implies ~ T(n) = \Theta\big((\log n)^{3/2}\big) \\ T(n) = T(n-\log n) + \frac{1}{n} ~ &\implies ~ T(n) = \Theta(\log\log n) \\ T(n) = T(n-\log^2 n) + \frac{1}{n} ~ &\implies ~ T(n) = \Theta(1)\end{align*}$$

Die gleiche Technik kann einer ähnlichen Klasse von Rekursiongleichungen gewidmet werden: die sogennante Teile-und-Herrsche Rekursionen, die sehr oft in der Lehre von theoretischen Algorithmen auftuachen und die Folgende Form annehmen:

$$T(n) = \alpha ~ T(n ~ / ~\beta) + a_n$$

wo $\alpha > 0$ und $\beta > 1$. Bevor man jene Technik anwendet muss man einen Ersatz durchführen: wenn man $c = \log_\beta\alpha$ definiert, dann kann man folgern

$$n^{-c} T(n) = (n/\beta)^{-c} ~ T(n ~ / ~\beta) + n^{-c} a_n$$

und man kann deshalb beweisen (hier verbergen wir viele mühsame Einzelkeiten, die mann in einem gültigen Beweis durcharbeiten muss), dass $T(n) = \Theta(n^c T^\ast(n))$, wo $T^\ast$ durch der folgenden Rekursionsgleichung definiert ist: $$T^\ast(n) = T^\ast(n/\beta) + \frac{a_n}{n^c}$$ Diese Rekursionsgleichung ist geeignet für unsere frühere Technik. Wenn $(a_n)$ mäßig ist, dann würde $T^\ast$ der gleichen Wachstumsklasse entsprechen, wenn wir es so definiert hätten: $$T^\ast(n) = T^\ast(n/\beta) + \sum_{k=n/\beta + 1}^n \frac{a_k}{k^{c+1}}$$ Wie früher, diese Rekursionsgleichung lässt sich ganz einfach durch einer analytischen Formel simplifizieren: $$T^\ast(n) = \sum_{k=1}^n \frac{a_k}{n^{c+1}}$$ damit $$T(n) = \Theta\bigg(n^c \sum_{k=1}^n \frac{a_k}{n^{c+1}}\bigg)$$ Also, insgesamt wissen wir (noch mal durch bestimmten Eigenschaften von $(a_n)$ bedingt), dass

$$T(n) = \alpha ~ T(n ~ / ~\beta) + a_n ~ \implies ~ T(n) = \Theta\bigg(n^c \sum_{k=1}^n \frac{a_k}{k^{c+1}}\bigg)$$

Diese Technik lässt sich auch in vielen Fällen anwenden, in den der sogennanten Master-Theorem wegen Beschränkungen auf $(a_n), \alpha, \beta$ leider nicht gilt, ohne auf fortgeschrittene Befunde z.B. von dem Kalkül zu beruhen. Zum Beispiel, hier sind ein paar von aus Rekursionsgleichungen entstandene asymptotische Formeln, die sich durch den Master-Theorem nicht lösen lassen:

$$\begin{align*}T(n) = T(n ~ / ~ 2) + \frac{1}{\log n} ~ &\implies ~ T(n) = \Theta(\log \log n) \\ T(n) = T(n ~ / ~ 2) + e^{\sqrt{\log n}} ~ &\implies ~ T(n) = \Theta\big(n\sqrt{\log n}\cdot e^{\sqrt{\log n}}\big) \\ T(n) = 2 ~ T(n ~ / ~ 2) + \frac{n\log\log n}{\log n} ~ &\implies ~ T(n) = \Theta(n \log^2\log n)\end{align*}$$