10 41.853
20 180.722
30 418.776
40 757.03
50 1194.007
60 1730.408
70 2369.747
80 3104.288
90 3939.342
100 4871.04332 Eigenschaften
32.1 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 \(\mathsf n_0 > 0\)
- ist \(\mathsf n_i\) gerade so ist \(\mathsf n_{i+1} = n_i/2\)
- ist \(\mathsf n_i\) ungerade so ist \(\mathsf n_{i+1} = 3n_i + 1\)
- endet bei \(\mathsf 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.
32.2 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
32.3 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
32.4 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 \(\mathsf f(n)\) gesucht, welche von der Problemgröße \(\mathsf 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 \(\mathsf g(n)\) mit \(\mathsf n \rightarrow \infty\), reduziert. Dabei beschränkt \(\mathsf g(n)\) das Wachstum von \(\mathsf f(n)\).
Die Funktion \(\mathsf g(n)\) wird oft durch ein \(\mathcal{O}\) gekennzeichnet und gibt so eine möglichst einfache Vergleichsfunktion an. Beispiele:
- \(\mathsf f_1(n) = n^4 + 5n^2 - 10 \approx \mathcal{O}(n^4) = g_1(n)\)
- \(\mathsf f_2(n) = 2^{n+1} \approx \mathcal{O}(2^n) = g_2(n)\)
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 \(\mathsf n\)) sei z.B. 1 s lang
- das \(\mathsf n\) sei beispielsweise 1000
Damit ergeben sich folgende (asymptotische) Abschätzungen der Laufzeit:
- \(\mathcal{O}(n)\): 103 s ≈ 1 h
- \(\mathcal{O}(n^2)\): 106 s ≈ 11 d
- \(\mathcal{O}(n^3)\): 109 s ≈ 31 a
- \(\mathcal{O}(2^n)\): 21000 s ≈ …
32.4.1 Komplexität Selectionsort
Die Kompexität dieses Verfahrens kann leicht abgeschätzt werden. Bei jedem Durchlauf wir das Minimum / Maximum gesucht, was anfangs \(\mathsf n\) Operationen benötigt. Beim nächsten Durchlauf sind es nur noch \(\mathsf n − 1\) Operationen und so weiter. In der Summe sind es also
\[ \mathsf 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 \(\mathcal{O}(n^2)\). Die folgende Abbildung verdeutlicht dies nochmals.
32.4.2 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: \(\mathcal{O} (n)\)
- worst case: \(\mathcal{O} (n^2)\)
- average case: \(\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 \(\mathsf n\) jeweils 10000 Listen sortiert. Es ist der Mittelwert und die minimalen und maximalen Operationen dargestellt.
10 42.0294
20 180.8565
30 419.1655
40 757.015
50 1194.4641
60 1730.8322
70 2367.9703
80 3105.6329
90 3941.6943
100 4877.1267
10 29.949
20 126.4037
30 304.2435
40 547.1489
50 904.231
60 1303.634
70 1869.3742
80 2445.0085
90 3206.351
100 3975.7806