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 Beschränkungen (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

• 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

• 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. jedes Element im Array entspricht dann einem Pixel.
• Puffern von Daten - Beim Lesen und Schreiben werden Daten meist in einem Array zwischengespeichert (gepuffert). Danach kann die Bearbeitung erfolgen. Weiters 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,...

Liste

Die Liste ist eine sehr gebräuchliche Datenstruktur. Sie ist gekennzeichnet durch, je nach implementierung, gute Zugriffszeiten oder erhöhte Flexibilität.
Beziehen wir uns auf die Programmiersprache Java, so ist die Liste ein Interface, das heißt eine Schnittstelle. Diese Schnittstelle definiert einige Methoden die eine Implementierung erfüllen muss. Einige davon wären:

• get(int index) - Gibt das Element an der Stelle index aus
• remove(int index) - Gibt das Element an der Stelle index aus
• add(E element) - Fügt ein Element an das Ende der Liste an
• ...

Hier ist nun ersichtlich, dass die Flexibilität der Liste ein essenzieller Bestandteil der Definition ist.
Anbei einige Implementierungen des Interfaces List.

ArrayList

Die ArrayList vereint die Eigenschaften einer Liste und eines Arrays. Die interne Implementierung verwendet ein Array von fixer größe um Elemente zu speichern. Wird diese fixe größe überschritten, so wird intern ein neues Array angelegt, je nach implementierung mit einem gewissen Vergrößerungsfaktor. Nach dem neuanlegen des internen Arrays, werden alle Elemente kopiert und in das neue Array eingefügt. Werden Elemente gelöscht, so müssen die Elemente nach dem gelöschten Element um eins nach links verschoben werden.

Element wird aus ArrayListe entfernt. Quelle: https://beginnersbook.com/2013/12/java-arraylist/

In Java wird die größe des internen Arrays nicht automatisch reduziert, wenn Elemente gelöscht werden. Dafür gibt es die Methode myArrayList.trim()

Vorteile

• Relativ geringer Speicheroverhead - Dies verhält sich ähnlich wie beim Array. Jedoch können in der ArrayList keine primitiven Datentypen gespeichert werden. Dies bedeutet, es wird nur ein Array von Referenzen erstellt. In jedem Platz findet sich eine Referenz auf das wirkliche Objekt. Dies bedeutet in Bezug auf primitive Datentypen einen weit höheren Speicherbedarf als bei einem Array.
• Geringe Zugriffszeit - Wird ein Element an einer stelle angesprochen, so kann für den Zugriff die Exakte Speicheradresse berechnet werden.

Nachteile

• Erhöhter Speicherbedarf - Erhöhter Speicherbedarf bei Verwendung von primitiven Datentypen, da diese in Klassendatentypen umgewandelt werden müssen.
• Ineffizientes Löschen - Laufzeit beim Löschen nicht optimal, Elemente müssen verschoben werden.
• Ineffizientes Hinzufügen, wenn internes Array voll - Laufzeit beim Hinzufügen von Elementen bei vollem Array langsam, ein neues Array muss erstellt werden und alle Elemente müssen kopiert werden.

Code beispiel

List<Integer> myArrayList = new ArrayList<>();
myArrayList.add(1);
myArrayList.add(1);
myArrayList.add(1);
myArrayList.remove(0);
System.out.println("Element an der Stelle 2: "+myArrayList.get(1));

• Zeile 1) Die die ArrayListe wird erzeugt und einer Variable des Typs List zugewiesen. Warum ist das möglich? Weil ArrayList das Interface List implementiert. D.h.: Eine ArrayList ist eine List.
• Zeile 2) - 4) fügen dem Array einen int hinzu. Hier ist zu beachten, der primitive Datentyp int wird automatisch in die Klasse Integer umgewandelt. Dieser mechanismus nennt sich Autoboxing.
• Zeile 5) Das Element an der Stelle 0 wird aus der ArrayList entfernt
• Zeile 6) Ausgabe des Elements an der Stelle 2 (Index 1)

Einsatzgebiete

Die Einsatzgebiete überschneiden sich mit herkömmlichen Arrays. Benötigt man mehr flexibilität und soll nicht mit primitiven Datentypen gearbeitet werden, so kann anstatt eines Arrays die ArrayListe verwendet werden. Ist die Anzahl der Elemente start fluktuierend, so sollte man aus oben genannten Gründen auf eine andere Datenstruktur ausweichen.

LinkedList oder verkettete Liste

Die verkettete Liste ist eine sehr dynamische Datenstruktur. Ihre Größe ist Flexibel. Die Daten werden in Knoten gehalten, welche im Falle der einfach verketteten Liste auf den Nachfolger und bei der doppelt verketteten Liste zusätzlich auf den Vorgänger Knoten zeigen.

Einfach und doppelt verkettete Liste. Quelle: https://www.java67.com/2016/01/how-to-implement-singly-linked-list-in-java-using-generics-example.html

Elemente können einfach an bestimmten Stellen eingefügt oder gelöscht werden, es müssen lediglich die Nachfolger bzw. Vorgänger aktualisiert werden.

Assoziatives Array

Das assoziative Array oder auch Map, ist eine Sammlung von Key, Value Paaren. Sie eignet sich sehr gut dafür, für einen bestimmten Schlüssel einen Wert zu hinterlegen. Die Operationen, einfügen, löschen, abrufen, sind Konstant und weisen im Normalfall ein Laufzeitverhalten von O(1) auf. Die Reihenfolge der Element ist nicht definiert.