Algorithmen und Datenstrukturen
Im folgenden Themenbereich geht es um Algorithmen und Datenstrukturen und um die Landau Symbole oder O - Notation und wie diese im Kontext von Algorithmen und Datenstrukturen verwendet wird.
Bei den Alghorithmen werden wir uns auf Sortieralgorithmen beschränken, uns mit deren Laufzeitanalyse (O - Notation) befassen
Bei den Datenstrukturen beschränken wir uns auf Arrays, Listen und Bäume und ebenfalls um deren Laufzeitanalyse für verschiedene Operationen
Landau Symbole oder O - Notation
Landau-Symbole (auch O-Notation) werden in der Mathematik und in der Informatik verwendet, um das asymptotische Verhalten von Funktionen und Folgen zu beschreiben. In der Informatik werden sie bei der Analyse von Algorithmen verwendet und geben ein Maß für die Anzahl der Elementarschritte oder der Speichereinheiten in Abhängigkeit von der Größe des gegebenen Problems an. (siehe [[1]]).
Unter asymptotischem Verhalten verstehen wir hier das Grenzverhalten eines Algorithmus, vereinfacht gesagt, wie kann sich die Laufzeit im schlechtesten Fall entwickeln.
In der O - Notation werden einige gebräuchliche Schranken verwendet, wenn wir einen Algorithmus oder eine Datenstruktur analysieren, verwenden wir diese Schranken und nicht die exakte Mathematische repräsentation des Problems (siehe Algorithmen_und_Datenstrukturen:Bubblesort)
| O - Notation | Bedeutung | Beispiel |
|---|---|---|
| O(1) | Das Laufzeitverhalten hängt nicht von der Anzahl der Elemente ab und ist konstant | Element an der Stelle N aus einem Array oder einer ArrayListe holen |
| O(n) | Das Laufzeitverhalten verlängert sich linear mit der Anzahl der Element | Suchen eines bestimmten Elements in einem unsortierten Array |
| O(n log n) | Super lineares Wachstum :-DDD | Mergesort, Heapsort, durchschnittsfall Quicksort |
| O(n2) | Quadratisches Wachstum, die Laufzeit wächst quadratisch zur Anzahl der Elemente | Bubblesort |