10 41.989
20 180.766
30 419.547
40 757.118
50 1193.255
60 1732.344
70 2365.573
80 3104.131
90 3941.413
100 4881.54430 Eigenschaften
30.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.
30.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
30.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
30.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 ≈ …
30.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.
30.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.0579
20 181.0355
30 419.407
40 756.5538
50 1194.3781
60 1732.2329
70 2368.4465
80 3105.4017
90 3941.7954
100 4878.1801
10 30.1403
20 126.7865
30 303.873
40 543.9807
50 907.6736
60 1316.7905
70 1860.8113
80 2447.6622
90 3206.3051
100 3969.7775