\( \newcommand{\data}{\textnormal{data}} \newcommand{\lower}{\textnormal{lower}} \newcommand{\upper}{\textnormal{upper}} \newcommand{\array}{\textnormal{array}} \newcommand{\depth}{\textnormal{depth}} \newcommand{\height}{\textnormal{height}} \newcommand{\BST}{\textnormal{BST}} \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\lognpone}{\ceil{\log_2(n+1)}} \newcommand{\bitsize}{\textnormal{bitSize}} \newcommand{\mult}{\textnormal{mult}} \newcommand{\inneighbors}{\textnormal{inNeighbors}} \newcommand{\outneighbors}{\textnormal{outNeighbors}} \newcommand{\neighbors}{\textnormal{neighbors}} \newcommand{\indeg}{\textnormal{indeg}} \newcommand{\outdeg}{\textnormal{outdeg}} \newcommand{\scc}{\textnormal{scc}} \newcommand{\R}{\mathbb{R}} \newcommand{\val}{\textnormal{val}} \newcommand{\dist}{\textnormal{dist}} \newcommand{\flows}{\textnormal{flows}} \)

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

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 \(\lognpone\). 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 Schreiben Sie in Python oder Elm eine Funktion rtbs (Abkürzung für runtime binary search), die \(\lognpone\) 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
\(n\) \(\lognpone\) \(\log_2(n)\) \(\frac{\lognpone}{\log_2(n)}\)
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 Rechnen Sie nun auf dem Papier: es ist wohl einfach zu zeigen, dass

\begin{align*} \lognpone \geq \log_2 n \end{align*}

gilt. Können Sie auch etwas in der Gegenrichtung zeigen, dass also \(\lognpone\) nicht viel größer ist? Also

\begin{align*} \lognpone \leq \log_2 n + (\textnormal{etwas kleines}) ? \end{align*}

Laufzeiten von Sortieralgorithmen

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

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

  • \(2 n H_n - 4n + 2H_n\) für Quicksort
  • \(3n (\ceil{\log_2(n+1)}-1)\) für Heapsort
  • \(n \ceil{\log_2 n} - 2^{\ceil{\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:
\(n\) \(2nH_n - 4n + 2H_n\) \(n \log_2(n)\) \( \frac{2nH_n - 4n + 2H_n}{n \log_2(n)}\)
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{align*} \lim_{n \rightarrow \infty} \frac{2nH_n - 4n + 2H_n}{n \log_2(n)} & = \lim_{n \rightarrow \infty} \left(2 \frac{H_n}{\log_2 n} - \frac{4}{\log_2 n} + \frac{2 H_n}{n \log_2 n}\right) \end{align*}

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} + \cdots + \frac{1}{n} \leq n\) ist eine extrem großzügige Abschätzung, genügt aber, um

\begin{align*} \lim_{n \rightarrow \infty} \frac{2 H_n}{n \log_2 n} \leq \lim_{n \rightarrow \infty} \frac{2 n}{n \log_2 n} = \lim_{n \rightarrow \infty} \frac{2}{\log_2 n} = 0 \end{align*}

zu zeigen. Insgesamt gilt also:

\begin{align*} \lim_{n \rightarrow \infty} \frac{2nH_n - 4n + 2H_n}{n \log_2(n)} & = \lim_{n \rightarrow \infty} 2 \frac{H_n}{\log_2 n} \end{align*}

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

\begin{align} \lim_{n \rightarrow \infty} 2 \frac{H_n}{\log_2 n} \geq \lim_{n \rightarrow \infty} 2 \frac{\ln (n) + \frac{1}{n}}{\log_2 n} \geq \lim_{n \rightarrow \infty} 2 \frac{\ln (n)}{\log_2 n} = 2 \ln (2) \ , \label{quicksort-rt-lower} \end{align}

da \(\ln(n) = \log_2(n) \ln(2)\) gilt. Die Abschätzung nach oben ist ähnlich:

\begin{align} \lim_{n \rightarrow \infty} 2 \frac{H_n}{\log_2 n} \leq \lim_{n \rightarrow \infty} 2 \frac{\ln(n) + 1}{\log_2 n} = \lim_{n \rightarrow \infty} \left( 2n \frac{\ln(n)}{\log_2 n} + \frac{1}{\log_2 n} \right) = \lim_{n \rightarrow \infty} 2 \frac{\ln(n)}{\log_2 n} = 2 \ln(2) \approx 1.38629\ . \label{quicksort-rt-upper} \end{align}

Wenn wir nun (\ref{quicksort-rt-lower}) und (\ref{quicksort-rt-upper}) kombinieren, dann erhalten wir

\begin{align*} \lim_{n \rightarrow \infty} \frac{2nH_n - 4n + 2H_n}{n \log_2(n)} & = 2 \ln(2) \approx 1.38629\ . \end{align*}

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

\begin{align*} \lim_{n \rightarrow \infty} \frac{n \ceil{\log_2 n} - 2^{\ceil{\log_2 n }} + 1}{n \log_2 n} & = 1 \tag{für Mergesort} \\ \lim_{n \rightarrow \infty} \frac{3n (\ceil{\log_2(n+1)}-1)}{n \log_2 n} & = 3 \tag{für Heapsort} \end{align*}