Eine harmonische Zahl ist eine Partialsumme der harmonischen Reihe. Die harmonischen Zahlen spielen eine wichtige Rolle in der Kombinatorik und daher auch für die Komplexitätsanalyse von Algorithmen. In dieser Blog-Folge zeige ich Dir, wie wir mithilfe der Integralrechnung gute Abschätzungen für die harmonischen Zahlen finden. Damit verbunden ist auch eine bekannte mathematische Konstante: die Euler-Mascheroni-Konstante.
Harmonische Zahlen
Wir beginnen mit der Definition der harmonischen Zahlen.
Definition
Die $n$-te Partialsumme $H_n$ der harmonischen Reihe heißt $n$-te harmonische Zahl: \[ H_n := \sum_{k=1}^n \frac{1}{k} = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}. \]Harmonische Zahlen werden immer wieder für die Komplexitätsanalyse von Algorithmen benötigt. Schauen wir uns dazu ein simples Beispiel in Java an.
public static void f(int n) {
for (int i=1 ; i<=n ; i++) {
int j=0;
while (j < n) {
...
j = j+i;
}
}
}
Angenommen, dort wo die Punkte ... stehen, würde eine Anweisung ausgeführt, die aus einer konstanten Anzahl an Operationen besteht. Dann wird der Aufwand der Funktion f bestimmt durch die Häufigkeit, mit der ... in Abhängigkeit von $n$ ausgeführt wird. Kannst Du hierfür direkt eine passende Funktion in $n$ angeben? Ich vermute nicht, denn die Häufigkeit der Ausführung von ... ändert sich mit wachsendem Iterationszähler $i$. Wir benötigen also eine genauere Analyse.
Für $i=1$ durchläuft $j$ die Zahlen $0,1,2,\ldots,n-1$. Die Anweisung ... wird also $n$ mal ausgeführt.
Für $i=2$ durchläuft $j$ aber die Zahlen $0,2,4,6,\ldots$ bis $n$ erreicht wird. Hier wird die Anweisung also nur noch für gerade Zahlen $j$ ausgeführt, also insgesamt $\lfloor \frac{n}{2} \rfloor$ oft. Da wir in der Informatik typischerweise an Worst-Case-Analysen interessiert sind, dürfen wir von $\frac{n}{2}$ Ausführungen ausgehen.
Für $i=3$ durchläuft $j$ die Zahlen $0,3,6,\ldots$ bis $n$ erreicht wird. Wir haben also höchstens $\frac{n}{3}$ Ausführungen von ....
Es folgt, dass die Anzahl der Ausführungen von ... insgesamt nach oben beschränkt ist durch \begin{eqnarray*} n + \frac{n}{2} + \frac{n}{3} + \cdots + \frac{n}{n} & = & n\left(1 + \frac{1}{2} + \cdots + \frac{1}{n} \right) \\[3mm] & = & n\cdot H_n. \end{eqnarray*} Mit der bekannten $O$-Notation können wir demnach von einem Aufwand von $O(n\cdot H_n)$ sprechen.
An dieser Stelle ist $O(n\cdot H_n)$ aber nicht aussagekräftig genug, denn wir kennen aktuell das Wachstum von $H_n$ in Abhängigkeit von $n$ nicht. Hier hilft uns der nachfolgende Satz.
Satz 1
Für alle $n\in\N$ gilt \[ \log(n+1) \leq H_n \leq 1 + \log(n). \]Den Nachweis für die Ungleichung führen wir mithilfe der Integralrechnung. Schau Dir diesen Beweis gut an, denn er zeigt am Beispiel der harmonischen Zahlen, wie solche Abschätzungen für Summen mittels Integralen funktionieren. Er ist also nicht nur ein Beweis, sondern auch ein Anwendungsbeispiel.
Beweis
Die folgende Skizze zeigt die Beweisidee am Beispiel von $H_4$.
Der Flächeninhalt der hellblauen Fläche entspricht der harmonischen Zahl $H_4$, denn die hellblauen Säulen haben die Höhen $1,\frac{1}{2},\frac{1}{3}$ und $\frac{1}{4}$ und jeweils die Breite $1$.
Dementsprechend ist die Fläche unter der roten Funktion $\frac{1}{x+1}$ zwischen $x=0$ und $x=4$ eine untere Schranke für $H_4$.
Eine obere Schranke erhalten wir, wenn wir die Fläche der linken Säule plus die Fläche unter der blauen Funktion $\frac{1}{x}$ zwischen $x=1$ und $x=4$ nehmen.
Zum Beweis rechnen wir die Schranken allgemein für $H_n$ einfach aus.
Für die untere Schranke ergibt sich: \begin{eqnarray*} H_n & \geq & \int_0^n \frac{1}{x+1}\,dx \\[2mm] & = & \left. \log(x+1) \right|_{x=0}^{x=n} \\[2mm] & = & \log(n+1) - \log(1) \\[2mm] & = & \log(n+1). \end{eqnarray*}
Für die obere Schranke erhalten wir: \begin{eqnarray*} H_n & \leq & 1 + \int_1^n \frac{1}{x}\,dx \\[2mm] & = & 1 + \left. \log(x)\right|_{x=1}^{x=n} \\[2mm] & = & 1 + \log(n) - \log(1) \\[2mm] & = & 1 + \log(n). \end{eqnarray*}
Damit ist die Ungleichung bewiesen.
Die harmonischen Zahlen wachsen also logarithmisch in Abhängigkeit von $n$. Mit der $O$-Notation schreibt man dies als \[ H_n = O(\log(n)) \quad \text{bzw.} \quad H_n = \Theta(\log(n)), \] je nachdem ob man ausdrücken möchte, dass die harmonischen Zahlen höchstens so schnell wachsen wie $\log(n)$ oder genau so schnell wie $\log(n)$.
Dementsprechen hat der oben formulierte Algorithmus einen Aufwand von $O(n\log(n))$.
Wegen \[ \log(n) \leq \log(n+1) \leq H_n \leq 1 + \log(n) \] können wir $H_n$ durch $\log(n+1)$ bzw. $1 + \log(n)$ mit einer Genauigkeit von $\leq 1$ abschätzen. Wenn wir als Abschätzung für $H_n$ das arithmetische Mittel dieser beiden Werte nehmen, können wir sogar eine Genauigkeit von $\frac{1}{2}$ garantieren. Unser Abschätzungsfehler ist damit insbesondere unabhängig von $n$, was eine sehr wünschenswerte Eigenschaft für Komplexitätsanalysen ist.
Euler-Mascheroni-Konstante
Für algorithmische Komplexitätsanalysen ist die Abschätzung von $H_n$ durch $\log(n)$ in der Regel vollkommen ausreichend. In der Mathematik können wir uns aber durchaus die Frage stellen, wie gut $H_n$ durch $\log(n)$ approximiert wird und wie sich die Differenz \[ H_n - \log(n) \] für $n$ gegen unendlich verhält. Dies wollen wir in diesem Abschnitt untersuchen.
Für diese Untersuchung werde ich zunächst eine Reihe von Hilfssätzen herleiten, mit denen wir dann die zentrale Aussage dieses Abschnitts leicht beweisen können.
Lemma 1
Es gilt \[ \lim_{n\rightarrow\infty} \log(n+1) - \log(n) = 0. \]Im folgenden Beweis für Lemma 1 nutzen wir Rechenregeln für den Logarithmus und die Stetigkeit der Logarithmusfunktion aus.
Beweis
Zunächst gilt \begin{eqnarray*} \log(n+1) - \log(n) & = & \log\left(\frac{n+1}{n}\right) \\[2mm] & = & \log\left(1 + \frac{1}{n}\right). \end{eqnarray*} Mit der Stetigkeit der Logarithmusfunktion folgt dann: \begin{eqnarray*} \lim_{n\rightarrow\infty} \log(n+1) - \log(n) & = & \lim_{n\rightarrow\infty} \log\left(1 + \frac{1}{n}\right) \\[2mm] & = & \log\left(\lim_{n\rightarrow\infty} 1 + \frac{1}{n}\right) \\[2mm] & = & \log(1) \\[2mm] & = & 0. \end{eqnarray*}Das nächste Lemma dient dazu, einen Bezug zu der Skizze für den Beweis von Satz 1 herzustellen, so dass sich eine anschauliche Interpration ergibt.
Lemma 2
Die Folge \[ (H_n - \log(n)) \] konvergiert genau dann, wenn die Folge \[ (H_n - \log(n+1)) \] konvergiert.Dieses Lemma ist im wesentlichen eine Konsequenz aus den Rechenregeln für Grenzwerte.
Beweis
Es gilt \[ H_n - \log(n) = (H_n - \log(n+1)) + (\log(n+1) - \log(n)). \]
In Lemma 1 haben wir gezeigt, dass $\log(n+1) - \log(n)$ konvergiert. Wenn nun $H_n - \log(n+1)$ konvergiert, dann folgt aus den Grenzwertregeln, dass auch $H_n - \log(n)$ konvergiert.
Andererseits gilt auch \[ H_n - \log(n+1) = (H_n - \log(n)) - (\log(n+1) - \log(n)). \] Wenn $H_n - \log(n)$ konvergiert, dann konvergiert nach Grenzwertregeln somit auch $H_n - \log(n+1)$.
Lemma 3
Die Folge \[ (H_n - \log(n+1)) \] ist konvergent.Beweis
Im Prinzip gehen wir ähnlich vor, wie beim Beweis des Integralkriteriums. Aus dem Beweis von Satz 1 wissen wir, dass \[ \log(n+1) = \int_0^n \frac{1}{x+1}\,dx \] gilt. Damit können wir wieder die Skizze aus dem Beweis von Satz 1 heranziehen und \[ H_n - \log(n+1) \] als die Differenz zwischen der blauen Fläche und der Fläche unter der roten Funktion $\frac{1}{x+1}$ interpretieren.
Es sei \[ \Delta_k := \frac{1}{k} - \int_{k-1}^k \frac{1}{x+1}\,dx. \] Damit ist $\Delta_k$ die Differenz zwischen der Fläche der $k$-ten Säule und der Fläche unterhalb von $\frac{1}{x+1}$ innerhalb der $k$-ten Säule, also gerade die $k$-te Dreiecksfläche in der oberen rechten Ecke der $k$-ten Säule.
Es folgt \[ H_n - \log(n+1) = \sum_{k=1}^n \Delta_k. \]
Wegen $\Delta_k \geq 0$ für $k\in\N$ ist damit $H_n - \log(n+1)$ eine monoton wachsende Folge.
Weiterhin gilt, dass $\Delta_k$ stets kleiner der Differenz zwischen dem Inhalt der $k$-ten und der $k+1$-ten Säule ist. D. h. \[ \Delta_k \leq \frac{1}{k} - \frac{1}{k+1} = \frac{1}{k^2+k}. \]
Damit folgt \[ H_n - \log(n+1) = \sum_{k=1}^n \Delta_k \leq \sum_{k=1}^n \frac{1}{k^2+k}. \]
Jetzt ist die Reihe \[ \sum_{n=1}^\infty \frac{1}{n^2+n} \] aber konvergent, woraus folgt, dass $H_n - \log(n+1)$ nach oben beschränkt ist.
Mit dem Satz der monotonen Konvergenz folgt, dass \[ (H_n - \log(n+1)) \] eine konvergente Folge ist.
Dies führt uns zum zentralen Satz dieses Abschnitts.
Satz 2
Die Folge \[ (H_n - \log(n)) \] ist konvergent.Beweis
Gemäß Lemma 3 ist die Folge \[ (H_n - \log(n+1)) \] konvergent. Weiterhin haben wir in Lemma 2 gezeigt, dass die Folge \[ (H_n - \log(n)) \] genau dann konvergent ist, wenn die Folge $(H_n - \log(n+1))$ konvergent ist.
Also ist die Folge \[ (H_n - \log(n)) \] ebenfalls konvergent.
Der existierende Grenzwert der Folge $(H_n - \log(n))$ ist eine wichtige mathematische Konstante, weshalb sie einen eigenen Namen hat.
Definition
Es sei \[ \gamma := \lim_{n\rightarrow\infty} (H_n - \log(n)). \] Die Zahl $\gamma$ heißt Euler-Mascheroni-Konstante.Wie groß ist denn nun die Euler-Mascheroni-Konstante $\gamma$? Die ersten hundert Nachkommastellen findest Du hier. Ihr Wert beträgt also \[ \gamma = 0.57721\,56649\,01532\,86060\,65120\,90082\,40243\,10421\,59335\,93992\ldots \]
Anwendung auf andere Funktionen
Natürlich kannst Du nicht nur die harmonischen Zahlen $H_n$ mithilfe von Integralen abschätzen. Du kannst die gleiche Technik auch analog für andere Summen anwenden, was für Komplexitätsanalysen ungemein hilfreich sein kann. Wir schauen uns dazu zwei Beispiele an.
Beispiel 1
Wie groß ist ungefähr \[ W_n := \sum_{k=1}^n \frac{1}{\sqrt{k}} = 1 + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + \cdots + \frac{1}{\sqrt{n}}\,? \]
Ein Ansatz analog zum Beweis von Satz 1 ergibt für eine Abschätzung nach oben: \begin{eqnarray*} W_n & \leq & 1 + \int_1^n \frac{1}{\sqrt{x}}\,dx \\[2mm] & = & 1 + 2\left.\sqrt{x}\right|_{x=1}^{x=n} \\[2mm] & = & 1 + 2\sqrt{n} - 2 \\[2mm] & = & 2\sqrt{n} - 1. \end{eqnarray*} Eine Abschätzung nach unten erhalten wir durch: \begin{eqnarray*} W_n & \geq & \int_0^n \frac{1}{\sqrt{x+1}}\,dx \\[2mm] & = & \left. 2\sqrt{x+1} \right|_{x=0}^{x=n} \\[2mm] & = & 2\sqrt{n+1} - 2. \end{eqnarray*}
Also gilt \[ 2\sqrt{n+1} - 2 \leq W_n \leq 2\sqrt{n} - 1 \] und somit \[ W_n = \Theta(\sqrt{n}). \] Damit kennen wir nun die Größenordnung von $W_n$.
Die Technik der Abschätzung von Summen durch Integrale können wir nicht nur für Summen $\sum_{k=1}^n f(k)$ mit monoton fallender Funktion $f(x)$ verwenden, sondern auch, wenn $f(x)$ monoton wachsend ist. Das nächste Beispiel zeigt, was wir dabei beachten müssen.
Beispiel 2
Zu Beginn dieser Blog-Folge haben wir die Java-Methode f(int n) implementiert und gezeigt, dass ihr Rechenaufwand $O(n\log(n))$ beträgt. Jetzt definieren wir eine Java-Methode g(int n), die f(k) mit $k=1,\ldots,n$ aufruft:
public static void g(int n) {
for (int k=1 ; k<=n ; k++) {
f(k);
}
}
Da jeder Aufruf von $f(k)$ bis auf einen konstanten Faktor den Aufwand $k\log(k)$ hat, ergibt sich als Gesamtaufwand für $g(n)$ (bis auf einen konstanten Faktor): \[ \sum_{k=1}^n k\log(k). \]
Wie groß ist nun ungefähr \[ L_n := \sum_{k=1}^n k\log(k) = 1\log(1) + 2\log(2) + \cdots + n\log(n)\,? \] Diesmal ist die Funktion $x\log(x)$, über die die Summe gebildet wird, monoton wachsend statt monoton fallend. Die nachfolgende Grafik skizziert das Vorgehen zur Abschätzung von $L_n$ analog zur Skizze aus Satz 1.
Jede Säule, deren rechte Seite sich an der Stelle $k$ befindet, hat die Höhe $k\log(k)$. Damit beträgt der Flächeninhalt der hellblauen Fläche $L_4$. Die blaue Funktion $(x+1)\log(x+1)$, die hier jetzt durch die linken Ecken der Säulen geht, dient wieder für eine Abschätzung nach oben. Dementsprechend liefert die rote Funktion $x\log(x)$ eine Abschätzung nach unten.
Mit partieller Integration lassen sich die Stammfunktionen ermitteln. Die genaue Herleitung überlasse ich Dir als Übung. Es gilt \[ \int x\log(x)\,dx = \frac{1}{2}x^2\log(x) - \frac{1}{4}x^2 + c \] und \[ \int (x+1)\log(x+1) = \left(\frac{1}{2}x^2+x\right)\log(x+1) - \frac{1}{4}x^2 + c. \]
Als Abschätzung nach oben erhalten wir: \begin{eqnarray*} L_n & \leq & \int_0^n (x+1)\log(x+1)\,dx \\[2mm] & = & \left[\left(\frac{1}{2}x^2+x\right)\log(x+1)-\frac{1}{4}x^2\right]_{x=0}^{x=n} \\[2mm] & = & \left(\frac{1}{2}n^2+n\right)\log(n+1) - \frac{1}{4}n^2. \end{eqnarray*}
Die Abschätzung nach unten lautet: \begin{eqnarray*} L_n & \geq & \int_1^n x\log(x)\,dx \\[2mm] & = & \left[\frac{1}{2}x^2\log(x) - \frac{1}{4}x^2\right]_{x=1}^{x=n} \\[2mm] & = & \frac{1}{2}n^2\log(n) - \frac{1}{4}n^2 +\frac{1}{4}. \end{eqnarray*}
Die am stärksten wachsenden Terme in den beiden Abschätzungen sind die $n^2\log(n)$ Terme. Damit folgt \[ L_n = \Theta(n^2\log(n)). \]
Die nächste Blog-Folge enthält einige Übungsaufgaben zur Abschätzung von Summen mithilfe von Integalen.
Teilen und Drucken