Eigenschaften

1.2.2. Eigenschaften#

Terminiertheit#

Terminiertheit bedeutet, dass ein Algorithmus nach endlich vielen Schritten anhält, oder er bricht kontrolliert ab. Einfache Beispiele:

  • Addition zweier Dezimalzahlen

  • Summe der ersten N natürlichen Zahlen

Allerdings kann die Terminiertheit nicht für alle Algerithmen gezeigt werden. Das Halteproblem besagt, dass es gibt keinen Verfahren gibt, welches immer zutreffend sagen kann, ob der Algorithmus für die Eingabe terminiert. Hierzu kann das Collatz-Problem als Beispiel herangezogen werden.

Die Zahlenfolge wird wie folgt konstruiert:

  • beginne mit irgendeiner natürlichen Zahl \(\sf n_0 > 0\)

  • ist \(\sf n_i\) gerade so ist \(\sf n_{i+1} = n_i/2\)

  • ist \(\sf n_i\) ungerade so ist \(\sf n_{i+1} = 3n_i + 1\)

  • endet bei \(\sf n_i = 1\)

Collatz-Vermutung: Jede so konstruierte Zahlenfolge mündet in den Zyklus 4, 2, 1, egal, mit welcher natürlichen Zahl man beginnt. Bisher unbewiesen.

Determiniertheit#

Ein deterministischer Algorithmus ist ein Algorithmus, bei dem nur definierte und reproduzierbare Zustände auftreten. Die Ergebnisse des Algorithmus sind somit immer reproduzierbar. Beispiele hierfür:

  • Addition ganzer Zahlen

  • Selectionsort

  • Collatz-Sequenz

Effizienz#

Die Effizienz eines Algorithmus ist nicht strikt definiert und kann folgende Aspekte umfassen:

  • Laufzeit

  • Speicheraufwand

  • Energieverbrauch

Bei bestimmten Anwendungen sind entsprechende Eigenschaften notwendig:

  • Speicheraufwand bei Big Data, also riesige Datenmengen, z.B. in der Bioinformatik

  • Laufzeit bei Echtzeitanwendung, z.B. Flugzeugsteuerung, Fußgängerdynamik

Komplexität#

Bei der Analyse von Algorithmen, gilt es die Komplexiät zu bestimmen, welche ein Maß für den Aufwand darstellt. Dabei wird nach einer Aufwandfunktion \(\sf f(n)\) gesucht, welche von der Problemgröße \(\sf n\) abhängt. Beispiel für eine Problemgröße:

  • Anzahl der Summanden bei einer Summe

  • Anzahl der zu sortierenden Zahlen

Meist wird dabei die Bestimmung auf eine asymptotische Analyse, d.h. eine einfache Vergleichsfunktion \(\sf g(n)\) mit \(\sf n \rightarrow \infty\), reduziert. Dabei beschränkt \(\sf g(n)\) das Wachstum von \(\sf f(n)\).

Die Funktion \(\sf g(n)\) wird oft durch ein \(\sf \mathcal{O}\) gekennzeichnet und gibt so eine möglichst einfache Vergleichsfunktion an. Beispiele:

  • \(\sf f_1(n) = n^4 + 5n^2 - 10 \approx \mathcal{O}(n^4) = g_1(n)\)

  • \(\sf f_2(n) = 2^{n+1} \approx \mathcal{O}(2^n) = g_2(n)\)

../../../_images/komplexitaet.svg

Fig. 1.19 Komplexität eines Algorithmus durch Vergleich einer Aufwandfunktion mit einer Vergleichsfunktion#

Um sich ein besseres Bild zu den Auswirkungen hoher Kompexitäten zu machen, sei folgendes Beispiel gegeben.

  • ein Berechnungsschritt (unabhängig von der Problemgröße \(\sf n\)) sei z.B. 1 s lang

  • das \(\sf n\) sei beispielsweise 1000

Damit ergeben sich folgende (asymptotische) Abschätzungen der Laufzeit:

  • \(\sf \mathcal{O}(n)\): 103 s ≈ 1 h

  • \(\sf \mathcal{O}(n^2)\): 106 s ≈ 11 d

  • \(\sf \mathcal{O}(n^3)\): 109 s ≈ 31 a

  • \(\sf \mathcal{O}(2^n)\): 21000 s ≈ …

Komplexität Selectionsort#

Die Kompexität dieses Verfahrens kann leicht abgeschätzt werden. Bei jedem Durchlauf wir das Minimum / Maximum gesucht, was anfangs \(\sf n\) Operationen benötigt. Beim nächsten Durchlauf sind es nur noch \(\sf n − 1\) Operationen und so weiter. In der Summe sind es also

\[ \sf f(n) = \sum_{i=0}^n i = \frac{n(n-1)}{2} \approx \mathcal{O}(n^2) \]

Damit hat der Selectionsort eine Komplexität von \(\sf \mathcal{O}(n^2)\). Die folgende Abbildung verdeutlicht dies nochmals.

../../../_images/sort_selection.svg

Fig. 1.20 Abschätzung der Koplexität des Selectionsort-Algorithmus#

Komplexität Bubblesort#

Die Komplexität des Bubblesort muss unterschieden werden in den günstigsten Fall (best case), den ungünstigsten Fall (worst case) und einem durchschnittlichen Fall (average case):

  • best case: \(\sf \mathcal{O}(n)\)

  • worst case: \(\sf \mathcal{O}(n^2)\)

  • average case: \(\sf \mathcal{O}(n^2)\)

Der best case ergibt sich zum Beispiel, falls die Eingabeliste bereits sortiert ist, da der Algorithmus nur einmal durch die Liste gehen muss, entsprechend n-Mal. Folgende Abbildung verdeutlicht die Anzahl der durchgeführten Operationen im Falle einer vollständig zufälligen Liste und einer, bei welcher 95% der Werte bereits sortiert ist. Dabei wurden für jedes \(\sf n\) jeweils 10000 Listen sortiert. Es ist der Mittelwert und die minimalen und maximalen Operationen dargestellt.

../../../_images/sort_bubble_p000.svg

Fig. 1.21 Abschätzung der Koplexität des Bubblesort-Algorithmus ohne Vorsortierung#

../../../_images/sort_bubble_p095.svg

Fig. 1.22 Abschätzung der Koplexität des Bubblesort-Algorithmus mit einer 95%-igen Vorsortierung#

Contents