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

3.1 Numerische Experimente und Grenzwerte

Erinnern Sie sich an die Anzahl von Array-Zugriffen, die die Binärsuche im Worst-Case macht? Das war $⌈ \log_{2} (n + 1) ⌉$ . Falls Sie diesen doch etwas komplizierten Ausdruck vergessen haben, können Sie sich wahrscheinlich merken, dass es ungefähr $\log_{2} (n)$ ist. Das Ziel dieses Kapitels ist, dieses ungefähr in einen mathematisch rigorosen Begriff umzuwandeln.

Übungsaufgabe 3.1.1 Schreiben Sie in Python oder Elm eine Funktion rtbs (Abkürzung für runtime binary search), die $⌈ \log_{2} (n + 1) ⌉$ zurückgibt. Schreiben Sie dann eine Funktion bl (für binary logarithm), der $\log_{2} n$ berechnet. Testen Sie dann, wie sich rtbs(n) / bl(n) (bzw. rtbs n / bl n, wenn Sie Elm schreiben) für große Werte von $n$ entwickelt.

Meine Lösung


10	4.000	3.322	1.204
100	7.000	6.644	1.054
1000	10.000	9.966	1.003
10000	14.000	13.288	1.054
100000	17.000	16.610	1.024
1000000	20.000	19.932	1.003

Übungsaufgabe 3.1.2 Rechnen Sie nun auf dem Papier: es ist wohl einfach zu zeigen, dass

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

gilt. Können Sie auch etwas in der Gegenrichtung zeigen, dass also $⌈ \log_{2} (n + 1) ⌉$ nicht viel größer ist? Also

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

Laufzeiten von Sortieralgorithmen

Vergleichen Sie nun die Laufzeiten der "guten" Sortieralgorithmen Quicksort, Mergesort und Heapsort mit den entsprechenden "einfacheren" Ausdrücken.

Übungsaufgabe 3.1.3 Die Anzahl der Vergleichsoperationen, die die guten Sortieralgorithmen aus dem letzten Kapitel im Worst-Case machen, sind

$2 n H_{n} - 4 n + 2 H_{n}$ für Quicksort
$3 n (⌈ \log_{2} (n + 1) ⌉ - 1)$ für Heapsort
$n ⌈ \log_{2} n ⌉ - 2^{⌈ \log_{2} n ⌉} + 1$ für Mergesort

All diese Ausdrücke sind schwer zu merken. Finden Sie vereinfachte Ausdrücke, die "ungefähr" gleich sind (wie oben bei der binären Suche) und verifizieren Sie experimentell, dass die Ausdrücke tatsächlich ungefähr gleich sind.

Tip: Verwenden Sie die Tatsache, dass $H_{n} \approx \ln n$ gilt.

Meine Ergebnisse für Quicksort:


10	24.437	33.219	0.736
100	647.850	664.386	0.975
1000	10985.913	9965.784	1.102
10000	155771.696	132877.124	1.172
100000	2018053.406	1660964.047	1.215
1000000	24785482.231	19931568.569	1.244
10000000	293906260.708	232534966.642	1.264

Asymptotik

Wenn Sie meine Werte für Quicksort betrachten, so kann man erkennen, dass der Wert langsam steigt. Ob er sich allerdings stabilisiert, und wenn ja, wo, lässt sich aus den Daten nicht ablesen. Um das zu klären, verwenden wir das Konzept des Grenzwertes.

\begin{aligned} lim_{n \to \infty} \frac{2 n H_{n} - 4 n + 2 H_{n}}{n \log_{2} (n)} & = lim_{n \to \infty} (2 \frac{H_{n}}{\log_{2} n} - \frac{4}{\log_{2} n} + \frac{2 H_{n}}{n \log_{2} n}) \end{aligned}

Der Ausdruck $\log_{2} n$ wird mit steigendem $n$ immer größer, und daher konvergiert $\frac{4}{\log_{2} n}$ gegen 0. Das selbe gilt für den dritten Term: $H_{n} = 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} \leq n$ ist eine extrem großzügige Abschätzung, genügt aber, um

\begin{array}{r} lim_{n \to \infty} \frac{2 H_{n}}{n \log_{2} n} \leq lim_{n \to \infty} \frac{2 n}{n \log_{2} n} = lim_{n \to \infty} \frac{2}{\log_{2} n} = 0 \end{array}

zu zeigen. Insgesamt gilt also:

\begin{aligned} lim_{n \to \infty} \frac{2 n H_{n} - 4 n + 2 H_{n}}{n \log_{2} (n)} & = lim_{n \to \infty} 2 \frac{H_{n}}{\log_{2} n} \end{aligned}

Um das noch weiter zu vereinfachen, verwenden wir die Ungleichung $\ln (n) + \frac{1}{n} \leq H_{n} \leq \ln (n) + 1$ . Daher:

\begin{array}{r} (1) & lim_{n \to \infty} 2 \frac{H_{n}}{\log_{2} n} \geq lim_{n \to \infty} 2 \frac{\ln (n) + \frac{1}{n}}{\log_{2} n} \geq lim_{n \to \infty} 2 \frac{\ln (n)}{\log_{2} n} = 2 \ln (2), \end{array}

da $\ln (n) = \log_{2} (n) \ln (2)$ gilt. Die Abschätzung nach oben ist ähnlich:

Wenn wir nun () und () kombinieren, dann erhalten wir

Übungsaufgabe 3.1.4 Führen Sie eine ähnliche Rechnung für Mergesort und Heapsort durch. Zeigen Sie also, dass

3. Laufzeitabschätzung mit O und Ω

3.1 Numerische Experimente und Grenzwerte

Laufzeiten von Sortieralgorithmen

Asymptotik

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