3. Laufzeitabschätzung mit $O$ und $\Omega$

3.2 Formale Definition von $O$ und $\Omega$

Fassen wir die Ergebnisse zusammen, die wir über die drei Sortieralgorithmen Quicksort, Mergesort und Heapsort erhalten haben: die Anzahl der Vergleichsoperationen im Worst-Case ist ungefähr

$n \log_2 n$ für Mergesort,
$2 n \ln n$ für Quicksort,
$3 n \log_2 n$ für Heapsort.

Alle drei Werte sind von der Form $C n \log n$ für eine Konstante $C$, die vom Algorithmus abhängt, aber nicht von der Inputgröße. Für die Sortieralgorithmen können wir den Wert von $C$ genau bestimmen. Im weiteren Verlauf der Vorlesung wird dies aber nicht immer möglich sein, und oft auch nicht interessant. Wir führen daher eine Definition ein, die uns erlaubt, dieses $C$ zu ignorieren.

Definition Seien $f, g : \N \rightarrow \R_0^+$ zwei Funktionen. Wir schreiben $f \in O(g)$, falls es Zahlen $n_0 \in \N$ und $C \gt 0$ gibt, so dass \begin{align*} f(n) \leq C \cdot g(n) \quad \forall n \geq n_0 \end{align*} gilt. Wir schreiben $f \in \Omega(g)$, falls es (womöglich andere) Zahlen $n_0 \in \N$ und $C \gt 0$ gibt, so dass \begin{align*} f(n) \geq C \cdot g(n) \quad \forall n \geq n_0 \end{align*} gilt. Wenn sowohl $f \in O(g)$ als auch $f \in \Omega(g)$, dann schreiben wir $f \in \Theta(g)$.

Am Besten lernen Sie, mit dieser Notation umzugehen, indem Sie Beispiele durchrechnen und Übungsaufgaben lösen.

Behauptung $\ceil{\log_2 (n+1)} \in O(\log_2 n)$.

Beweis. Wir müssen zeigen, dass $\ceil{\log_2 (n+1)} \leq C \log_2 n$ gilt, zumindest für große Werte von $n$. Dabei dürfen wir frei wählen, was $C$ ist und was "große Werte" bedeutet. Um einen Anfang zu machen, schreiben wir einfach mal $\ceil{\log_2 (n+1)}$ hin und schätzen es nach oben ab: \begin{align*} \ceil{\log_2 (n+1)} & \leq \log_2 (n+1) + 1 \\ & \leq \log_2 (2n) + 1 \tag{falls $n \geq 1$} \\ & = \log_2 n + 2 \ . \end{align*}

Das ganze soll nun $\leq C \log_2 n $ sein. Wie sollen wir $C$ wählen? Probieren wir mal $C = 2$ aus:

\begin{align*} \log_2 n + 2 & \stackrel{?}{\leq} 2 \cdot \log_2 n \quad \Leftrightarrow \\ 2 & \stackrel{?}{\leq} \log_2 n \quad \Leftrightarrow \\ 4 & \stackrel{?}{\leq} n \ . \end{align*}

Wir schließen also: für alle $n \geq 4$ gilt $\ceil{\log(n+1)} \leq 2 \log_2 n $. Wir wählen also $n_0 := 4$ und $C := 2$; damit gilt $\ceil{\log_2(n+1)} \in O(\log_2 n)$.

Bitte beachten Sie, dass wir bei der Wahl von $C \in \R^+$ und $n_0 \in \N$ recht viel Freiheit haben. Probieren wir die obige Rechnung also nochmal mit $C := 1.1$:

\begin{align*} \log_2 n + 2 & \stackrel{?}{\leq} 1.1 \cdot \log_2 n \quad \Leftrightarrow \\ 2 & \stackrel{?}{\leq} 0.1 \log_2 n \quad \Leftrightarrow \\ 20 & \stackrel{?}{\leq} \log_2 n \quad \Leftrightarrow \\ n & \stackrel{?}{\leq} 2^{20} \ . \end{align*} Die gleiche Rechnung funktioniert also auch für $C = 1.1$, allerdings allerdings erst für rechts große Werte $n$, nämlich für $n \geq n_0 := 2^{20}$.

Behauptung $\ceil{\log_2 (n+1)} \in \Omega(\log_2 n)$.

Beweis. Dies ist viel einfacher: \begin{align*} \ceil{\log_2 (n+1)} \leq \log_2 (n+1) \leq \log_2 n \ , \end{align*} und somit können wir $C=1$ und $n_0 = 1$ setzen.

Wir haben also gezeigt, dass $\ceil{\log_2 (n+1)}\in \Theta(\log_2 n)$ gilt.

Übungsaufgabe Zeigen Sie, dass die Worst-Case-Anzahl der Vergleichsoperationen in Quicksort, Mergesort und Heapsort alle $\Theta(n \log n)$ sind, also

$n \log_2 n \in \Theta(n \log n) $,
$2 n \ln n \in \Theta(n \log n)$,
$3 n \log_2 n \in \Theta(n \log n)$.

Übungsaufgabe SelectionSort macht $n (n-1) / 2$ Vergleichsoperationen. Zeigen Sie, dass dies $\Theta(n^2)$ ist.

Zeigen Sie, dass auch $\frac{n(n+1)}{2} \in \Theta(n^2)$ ist.

Erinnern Sie sich an den Binomialkoeffizienten ${n \choose k}$. Dies ist definiert als die Anzahl der $k$-elementigen Teilmengen der Menge $\{1,2,\dots,n\}$. Es gilt

\begin{align*} {n \choose k} = \frac{n!}{(n-k)!k!} \ . \end{align*}

Übungsaufgabe Zeigen Sie, dass ${n \choose 3} \in \Theta(n^3)$ gilt, ${n \choose 4} \in \Theta(n^4)$ und ganz generell ${n \choose k} \in \Theta(n^k)$ für jede natürliche Zahl $k$ gilt.

Summen

In der Analyse von Algorithmen treten häufig Summen auf. Da ist es besonders wichtig, diese durch einen prägnanten Ausdruck abzuschätzen.

Übungsaufgabe Zeigen Sie, dass \begin{align*} \sum_{k=1}^n k^2 \in \Theta(n^3) \end{align*} gilt.

Tip: Versuchen Sie nicht, eine geschlossene Formel für die Summe zu finden.

Übungsaufgabe Sei $a > 1$ eine beliebige Zahl. Zeigen Sie, dass

\begin{align*} \sum_{k=1}^n a^k \in \Theta(a^n) \end{align*}

gilt. In Worten: eine geometrische Summe wird durch ihren höchsten Term dominiert.

Übungsaufgabe Zeigen Sie, dass

\begin{align*} \sum_{k=1}^n k 2^k \in \Theta(n2^n) \end{align*}

gilt.

Übungsaufgabe Zeigen Sie, dass $n^4 \in O(2^n)$ gilt.

Tip: Verwenden Sie die Tatsache, dass $2^n = {n \choose 1} + {n \choose 2 } + {n \choose 3} + \cdots + {n \choose n-1} + {n \choose n}$ ist.

Übungsaufgabe Zeigen Sie, dass $n^4 \in O(1.3^n)$ gilt.

Übungsaufgabe Zeigen Sie ganz allgemein, dass $n^k \in O(c^n)$ für alle $k \in \N$ und $c \gt 1$.

Das $O$ ist also die asymptotische Entsprechung des Vergleichsoperators $\leq$. Was wäre eine asymptotische Version von $\lt$? Wie können wir beispielsweise ausdrücken, dass Quicksort asymptotisch echt besser ist als Selectionsort?

Definition Seien $f, g : \N \rightarrow \R_0^+$ zwei Funktionen. Wir schreiben $f \in o(g)$, falls es für jede Zahl $C \gt 0$ eine Zahl $n_0 \in \N$ gibt, so dass \begin{align*} f(n) \leq C \cdot g(n) \quad \forall n \geq n_0 \end{align*} gilt. Äquivalent können wir $\lim_{n \rightarrow \infty} \frac{f(n)}{g(n)} = 0$ schreiben. Wir schreiben $f \in \omega(g)$, falls es für jede Zahl $C \in \R$ eine Zahl $n_0 \in \N$ gibt, so dass \begin{align*} f(n) \geq C \cdot g(n) \quad \forall n \geq n_0 \end{align*} gilt. Äquivalent können wir $\lim_{n \rightarrow \infty} \frac{f(n)}{g(n)} = +\infty$ schreiben.

Übungsaufgabe Zeigen Sie, dass $n \log n \in o(n^2)$.

3. Laufzeitabschätzung mit \(O\) und \(\Omega\)

3.2 Formale Definition von \(O\) und \(\Omega\)

Summen