3. Laufzeitabschätzung mit $O$ und $Ω$

3.2 Formale Definition von $O$ und $Ω$

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 3.2.1 Seien

f, g : N \to R_{0}^{+}

zwei Funktionen. Wir schreiben

f \in O (g)

, falls es Zahlen

n_{0} \in N

und

C > 0

gibt, so dass

\begin{array}{r} f (n) \leq C \cdot g (n) \forall n \geq n_{0} \end{array}

gilt. Wir schreiben

f \in Ω (g)

, falls es (womöglich andere) Zahlen

n_{0} \in N

und

C > 0

gibt, so dass

\begin{array}{r} f (n) \geq C \cdot g (n) \forall n \geq n_{0} \end{array}

gilt. Wenn sowohl

f \in O (g)

als auch

f \in Ω (g)

, dann schreiben wir

f \in Θ (g)

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

Behauptung 3.2.2

⌈ \log_{2} (n + 1) ⌉ \in O (\log_{2} n)

Beweis. Wir müssen zeigen, dass

⌈ \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

⌈ \log_{2} (n + 1) ⌉

hin und schätzen es nach oben ab:

\begin{aligned} ⌈ \log_{2} (n + 1) ⌉ & \leq \log_{2} (n + 1) + 1 \\ (falls n \geq 1) & \leq \log_{2} (2 n) + 1 \\ = \log_{2} n + 2 . \end{aligned}

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

\begin{aligned} \log_{2} n + 2 & \overset{?}{\leq} 2 \cdot \log_{2} n \Leftrightarrow \\ 2 & \overset{?}{\leq} \log_{2} n \Leftrightarrow \\ 4 & \overset{?}{\leq} n . \end{aligned}

Wir schließen also: für alle $n \geq 4$ gilt $⌈ \log (n + 1) ⌉ \leq 2 \log_{2} n$ . Wir wählen also $n_{0} := 4$ und $C := 2$ ; damit gilt $⌈ \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{aligned} \log_{2} n + 2 & \overset{?}{\leq} 1.1 \cdot \log_{2} n \Leftrightarrow \\ 2 & \overset{?}{\leq} 0.1 \log_{2} n \Leftrightarrow \\ 20 & \overset{?}{\leq} \log_{2} n \Leftrightarrow \\ n & \overset{?}{\leq} 2^{20} . \end{aligned}

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 3.2.3

⌈ \log_{2} (n + 1) ⌉ \in Ω (\log_{2} n)

Beweis. Dies ist viel einfacher:

\begin{array}{r} ⌈ \log_{2} (n + 1) ⌉ \leq \log_{2} (n + 1) \leq \log_{2} n, \end{array}

und somit können wir

C = 1

und

n_{0} = 1

setzen.

Wir haben also gezeigt, dass $⌈ \log_{2} (n + 1) ⌉ \in Θ (\log_{2} n)$ gilt.

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

$n \log_{2} n \in Θ (n \log n)$ ,
$2 n \ln n \in Θ (n \log n)$ ,
$3 n \log_{2} n \in Θ (n \log n)$ .

Übungsaufgabe 3.2.2 SelectionSort macht $n (n - 1) / 2$ Vergleichsoperationen. Zeigen Sie, dass dies $Θ (n^{2})$ ist.

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

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

\begin{array}{r} (\binom{n}{k}) = \frac{n!}{(n - k)! k!} . \end{array}

Übungsaufgabe 3.2.3 Zeigen Sie, dass $(\binom{n}{3}) \in Θ (n^{3})$ gilt, $(\binom{n}{4}) \in Θ (n^{4})$ und ganz generell $(\binom{n}{k}) \in Θ (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 3.2.4 Zeigen Sie, dass gilt.

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

Übungsaufgabe 3.2.5 Sei eine beliebige Zahl. Zeigen Sie, dass

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

Übungsaufgabe 3.2.6 Zeigen Sie, dass

gilt.

Übungsaufgabe 3.2.7 Zeigen Sie, dass gilt.

Tip: Verwenden Sie die Tatsache, dass ist.

Übungsaufgabe 3.2.8 Zeigen Sie, dass gilt.

Übungsaufgabe 3.2.9 Zeigen Sie ganz allgemein, dass für alle und .

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

Definition 3.2.4 Seien zwei Funktionen. Wir schreiben , falls es für jede Zahl eine Zahl gibt, so dass gilt. Äquivalent können wir schreiben. Wir schreiben , falls es für jede Zahl eine Zahl gibt, so dass gilt. Äquivalent können wir schreiben.

Übungsaufgabe 3.2.10 Zeigen Sie, dass .

3. Laufzeitabschätzung mit O und Ω

3.2 Formale Definition von O und Ω

Summen

3. Laufzeitabschätzung mit $O$ und $Ω$

3.2 Formale Definition von $O$ und $Ω$