Was wird gezählt?

Wesentlich für den Aufwand sind Schlüsselvergleiche und Datenumspeicherungen. Mit Datenumspeicherung ist die Bewegung eines kompletten Datensatzes gemeint.

best case, worst case, average case

Dabei betrachten wir folgende drei Fälle:

"best case": Wie viele Schlüsselvergleiche bzw. Datenumspeicherungen werden mindestens, d.h. im besten Fall durchgeführt?
(Bezeichnung: $V_{min}$ bzw. $U_{min}$ )
"worst case": Wie viele Schlüsselvergleiche bzw. Datenumspeicherungen werden höchstens, d.h. im schlechtesten Fall durchgeführt?
(Bezeichnung: $V_{max}$ bzw. $U_{max}$ )
"average case": Wie viele Schlüsselvergleiche bzw. Datenumspeicherungen werden im Mittel durchgeführt?
(Bezeichnung: $V_{mid}$ bzw. $U_{mid}$ )

Wie wird gezählt?

In der Regel ist die Anzahl an Schlüsselvergleichen oder Datenumspeicherungen abhängig von der Anzahl $n$ der Datensätze. Bei der Aufwandsanalyse interessiert uns nicht eine genaue Anzahl, sondern - im Sinne einer Größenordnung - nur die Terme in $n$ , die am schnellsten wachsen.

Um das auszudrücken, verwenden wir die nachfolgend beschriebene " $\mathcal{O}$ -Notation". Vereinfacht gesagt notieren wir

$f(n)= \mathcal{O}(g(n))$ ,

wenn für $n$ gegen $\infty$ der Quotient $f(n)/g(n)$ beschränkt bleibt. Die Funktion $f$ wächst also höchstens so schnell wie $g$ .

Die exakte Definition lautet:

Definition

Sind $f, g : \mathbb{N} \to \mathbb{R}^+$ zwei Funktionen, so ist $f = \mathcal{O}(g)$ genau dann,
wenn: $\exists n_0 \in \mathbb{N}, \, c>0 : f(n) \leq c \cdot g(n)$ für alle $n \geq n_0.$

Einige Beispiele:


$2 \cdot n^2$	$\quad = \quad$	$\mathcal{O}(n^2)$
$n^2 + 3 \cdot n + 4$	$\quad = \quad$	$\mathcal{O}(n^2)$
$3 \cdot n \cdot \log(n) + 2 \cdot n$	$\quad = \quad$	$\mathcal{O}(n \cdot \log(n))$

oder auch:


$n^2 + 3 \cdot n + 4$	$\quad = \quad$	$n^2 + \mathcal{O}(n)$
$3 \cdot n \cdot \log(n) + 2 \cdot n$	$\quad = \quad$	$3 \cdot n \cdot \log(n) + \mathcal{O}(n)$
$\frac{n}{2} + 5$	$\quad = \quad$	$\frac{n}{2} + \mathcal{O}(1)$

a)	Testen Sie, wie viele Schüsselvergleiche und wie viele Umspeicherungen die verschiedenen Verfahren durchführen, wenn die Werte anfangs aufsteigend bzw. absteigend sortiert sind.
b)	Vergleichen Sie die ermittelten Werte mit den Aufwandsabschätzungen.

a)
b)
c)	Wie viele Umspeicherungen benötigt man insgesamt bei den vier Sortierverfahren, um die Schlüssel aufsteigend zu sortieren.