Die Effizienz von Algorithmen ist in den meisten Fällen vom Ausgangszustand der Datenmenge abhängig.
Besonders interessant wird es bei Sortieralgorithmen
Bei der Komplexität wird zwischen Best Case (Ω-Notation), Average Case (Θ-Notation) und Worst Case (O-Notation) unterschieden.
Welcher Algorithmus im Endeffekt als "bester" bezeichnet werden kann, muss immer individuell und situativ entschieden werden.
Zwei Entscheidungsfaktoren bezüglich der Komplexität sind dabei die Laufzeit und der benötigte Speicherplatz des Algorithmus.
Bei der Komplexität orientiert man sich immer am Worst Case, also der O-Notation.
Die Tabelle zeigt die Bedeutung der verschiedenen Notationsgrößen auf.
n ... Eingabegröße
| Notation | Bezeichnung | Bedeutung |
|---|---|---|
| O(1) | Konstante(r) Zeit/Speicherplatz | bleibt konstant |
| O(log n) | Logarithmische(r) Zeit/Speicherplatz | wächst logarithmisch |
| O(n) | Lineare(r) Zeit/Speicherplatz | wächst linear |
| O(n log n) | Linearithmische(r) Zeit/Speicherplatz | wächst in der Nähe linear |
| O(n^2) | Quadratische(r) Zeit/Speicherplatz | wächst quadratisch |
| O(2^n) | Exponentielle(r) Zeit/Speicherplatz | wächst exponentiell |
| O(n!) | Faktorielle(r) Zeit/Speicherplatz | wächst faktoriell |
Multiplizieren
Addieren
Die Laufzeitkomplexität eines Algorithmus gibt an, wie sich die Ausführungszeit des Algorithmus mit zunehmender Eingabegröße verhält.
Beispiel:
Die Liste ist von Beginn an korrekt sortiert.
Hier brauchen die meisten Sortieralgorithmen weniger Zeit zum Sortieren.
Das wäre dann der beste Fall, da der Algorithmus dadurch noch effizienter ist.
Die Laufzeitkomplexität kann mit Hilfe der Tabelle bestimmt werden.
| Programmteil | Laufzeitkomplexität | Beispiel |
|---|---|---|
| Anweisung | O(1) | x = 5 |
| Schleifen | O(n) | for i in range(n): print(i) |
| Verschachtelte Schleifen | O(n^2), O(n^3), usw. | for i in range(n): for j in range(n): print(i, j) |
| Rekursion (abhängig von der Tiefe) | Variiert | def factorial(n): if n == 0: return 1 else: return n * factorial(n-1) |
Beschreibt, wie sich der zusätzliche Speicherbedarf eines Algorithmus mit zunehmender Eingabegröße ändert.
Wichtig, um sicherzustellen, dass ein Algorithmus nicht unnötig viel Speicherplatz beansprucht.
| Programmteil | Speicherkomplexität | Beispiel |
|---|---|---|
| Einfache Variablen | O(1) | x = 5 |
| Arrays oder Listen | O(n) | arr = [1, 2, 3, ..., n] |
| Verschachtelte Datenstrukturen | Variiert | matrix = [[1, 2], [3, 4], ..., [n, n]] |
| Rekursion (abhängig von der Tiefe) | Variiert | def factorial(n): if n == 0: return 1 else: return n * factorial(n-1) |