11  Beurteilung von Algorithmen

Die Effizienz eines Algorithmus kann grundsätzlich nach seinem Rechenaufwand oder Speicherbedarf beurteilt werden. Man spricht in diesem Zusammenhang auch von Zeit- bzw. Platzkomplexität.

Wir haben uns mit dem Zählen von Vergleichen nur mit der Rechenaufwand, also mit der Zeitkomplexität beschäftigt. Die Berechnungen werden sehr stark vereinfacht.

11.1 Bubblesort

Wenn wir mit dem Bubblesort \(n\) Objekte sortieren, haben wir \(n-1\) Vergleiche im ersten Durchgang. Vereinfacht sagen wir einfach \(n\) Vergleiche. Im schlimsten Fall, müssen ist das kleinste Element am falschen Ende. Bei jedem Durchgang verschieben wir das Element nur um einen Platz. Dass heisst wir müssen etwa \(n\) Durchgänge machen. Die Laufzeit vom Bubblesort beträgt somit \(n \cdot n = n^2\).

11.2 Mergesort

Mergesort_example

Bevor wir uns die Laufzeit von Mergesort anschauen, müssen wir quantifizieren, wie oft wir die Listen aufteilen müssen. Haben wir 2 Elemente, separieren wir 1 Mal. Haben wir 4 Elemente separieren wir 2 mal.

len	Teilungen
2	1
4	2
8	3
16	4
32	5
64	6
1024	10

Diese Funktion, welche der Länge zur Anzahl Teilungen zuordnet, nennt man Logarithmus zur Basis 2. Man notiert sie wie folgt: \(\log_2(n)\)

Auf jeder der \(\log_2(n)\) Ebene machen wir etwa \(n\) Vergleiche. Die Laufzeit vom Mergesort beträgt somit \(n \cdot \log_2(n)\).

Mergesort_example