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 Bubblesort)

Gebräuchliche Schranken (es gibt viele weitere!)

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
O(log2n)	2er Logarithmisches Wachstum	Suche im Binärbaum

Datenstrukturen

In der Informatik und Softwaretechnik ist eine Datenstruktur ein Objekt, welches zur Speicherung und Organisation von Daten dient. Es handelt sich um eine Struktur, weil die Daten in einer bestimmten Art und Weise angeordnet und verknüpft werden, um den Zugriff auf sie und ihre Verwaltung effizient zu ermöglichen. (siehe [[2]])

Im folgenden sollen einige Datenstrukturen erläutert werden, für jede Datenstruktur gibt es andere Einsatzgebiete die für deren Eigenschaften optimal sind.

Array

Ein Array oder Feld ist eine sehr effiziente doch wenig dynamische Datenstruktur. In nahezu allen Programmiersprachen findet sich diese Datenstruktur wieder. Weiter ist auch ein dynamisches vergrößern oder verkleinern in einigen Programmiersprachen automatisch implementiert (Javascript).
Gehen wir jedoch von Programmiersprachen wie Java oder C aus, so hat ein Array immer eine fixe größe. Das heißt, zur Laufzeit (nach dem das Programm compiliert und gestartet wurde) kann diese nicht verändert werden.

Vorteile von Arrays

• Der Speicheroverhead ist sehr gering - Es wird nur der Speicher reserviert, der für die Anzahl der Elemente benötigt wird.
• Geringe Zugriffszeit - Wird ein Element an einer stelle angesprochen, so kann für den Zugriff die Exakte Speicheradresse berechnet werden.

Nachteile von Arrays

• Wenig flexibel - Wie bereits erwähnt, muss die größe meist fix definiert werden. Eine vergrößerung/verkleinerung ist nicht möglich, ermöglicht die Programmiersprache dies, so hat dies meist zurfolge, dass das Array neu erstellt wird, und die Elemente kopiert werden müssen.

Einsatzgebiete

Überall dort, wo eine fixe Speichergröße benötigt und effizient wichtig ist, dort sollte die Verwendung von Arrays in betracht gezogen werden.

• Bildmanipulation - Wird ein Bild zur Bearbeitung geladen, so kann die Bitmap in einem Array gespeichert werden.
• Puffern von Daten - Beim Lesen und Schreiben, werden Daten meist in einem Array zwischengespeichert (gepuffert). Hierbei kann bei jedem Lese oder Schreibvorgang erneut das selbe Array verwendet werden, was die Effizienz weiter erhöht.
• Jegliches Schachbrettartige Problem mit fixer Größe - Schiffe versenken, Schach,...