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(n²)	Quadratisches Wachstum, die Laufzeit wächst quadratisch zur Anzahl der Elemente	Bubblesort
O(log₂n)	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:

E get(int index) - Gibt das Element an der Stelle index aus
E remove(int index) - Gibt das Element an der Stelle index aus
boolean add(E element) - Fügt ein Element an das Ende der Liste an
boolean add(int index, E element) - Fügt ein Element an einer bestimmten Position ein, und schiebt nachfolgende Elemente nach rechts (Index wird erhöht)
...

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.

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

Ineffizientes Löschen - Laufzeit beim Löschen nicht optimal, Elemente müssen verschoben werden.
Ineffizientes Einfügen - Laufzeit beim Einfügen von Elementen an einer gewissen Stelle langsam, wie beim löschen müssen alle Nachfolgenden Elemente 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

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 (oftmaliges löschen/einfügen/hinzufügen), 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. Elemente können einfach an bestimmten Stellen eingefügt oder gelöscht werden, es müssen lediglich die Nachfolger bzw. Vorgänger aktualisiert werden.

Vorteile

Einfügen und Löschen effizient - Es müssen lediglich die Zeiger auf den Vorgänger/Nachfolger geändert werden.

Nachteile

Zufälliger Zugriff langsam - Werden in der LinkedList Elemente mit ihrem Index angesprochen, so muss zuerst die komplette Liste bis zum entsprechenden Index durchlaufen werden.
Speicheroverhead - Da die Daten in Knoten gespeichert werden müssen entsteht automatisch ein Speicheroverhead.

Einsatzgebiete

Wenn die größe der Liste stark variiert, d.h. oftmals Elemente eingefügt, gelöscht und hinzugefügt werden und kein zufälliger Zugriff benötigt wird.

Code beispiel

Hinzufügen eines Elements

public boolean add(Integer element) {
  Node newNode = new Node(element);
  if(root == null) {
    root = newNode;
  } else {
    Node current = root;
    while(current.next() != null) {
      current = current.next();
    }
    current.setNext(newNode);
  }
  return true;
}

Holen eines Elements

public Integer get(int index) {
  Node current = root;
  for(int i=0; i<index && current != null; i++) {
    current = current.next();
  }
  if(current == null) {
    throw new IndexOutOfBoundsException();
  }
}

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.

Sortieralgorithmen

Sortieralgorithmen werden benötigt um Datenstrukturen nach gewissen Kriterien zu sortieren. Dazu müssen die Elemente natürlich vergleichbar sein, d.h. es muss möglich sein herauszufinden ob ein Element "größer" oder "kleiner" als ein anderes ist.

Eigenschaften

Sortieralgorithmen können über mehrere Eigenschaften verfügen.

In-Place

Das bedeutet der Sortieralgorithmus benötigt "keinen" weiteren Speicherplatz beim sortieren, bzw. wenn der Speicherbedarf konstant ist, und nicht mit der Anzahl der Elemente wächst. Z.b. der Sortieralgorithmus Mergesort, teilt die Daten der bestehenden Liste in Sublisten auf, er ist somit nicht In-Place.

Stabil

Ein Sortieralgorithmus arbeitet stabil, wenn dieser eine bestehende korrekte Ordnung nicht verändert.

Bubblesort

Bubblesort ist ein vergleichsweise akademischer Algorithmus. Er ist wenig effizient, arbeitet jedoch Stabil und In-Place.

Code

Bubblesort in Java

public class Bubblesort {
	public static void sort(int[] arr) {
		int operations = 0;
		int n = arr.length;
		boolean swapped = false;
		do {
			swapped = false;
			for (int i = 0; i < n - 1; i++) {
				operations++;
				if (arr[i] > arr[i + 1]) {
					int tmp = arr[i];
					arr[i] = arr[i + 1];
					arr[i + 1] = tmp;
					swapped = true;
				}
			}
			// Letztes Element ist an der richtigen stelle, n um 1 reduzieren
			n = n - 1;
		} while (swapped);
		System.out.println("Operations: " + operations);
	}

	public static void main(String[] args) {
		int[] arr = new int[] { 1, 2, 3, 4, 5, 6 };
		sort(arr);
		arr = new int[] { 6, 5, 4, 3, 2, 1 };
		sort(arr);
		arr = new int[] { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
		sort(arr);
	}
}

Laufzeitanalyse

Für die Laufzeitanalyse verwenden wir die maximal mögliche Laufzeit. Betrachten wir hierfür folgendes Array: 10,8,5,3,2,1

1) Durchlauf: Die Zahl 10 wird mit 8,5,3,2 und 1 verglichen und vertauscht.
2) Durchlauf: Die Zahl 8 wird mit 5,3,2 und 1 verglichen und vertauscht, mit 10 muss nichtmehr verglichen werden.
3) Durchlauf: Die Zahl 5 wird mit 3,2 und 1 verglichen und vertauscht, mit 10, 8 muss nichtmehr verglichen werden.
4) Durchlauf: Die Zahl 3 wird mit 2 und 1 verglichen und vertauscht, mit 10, 8, 5 muss nichtmehr verglichen werden.
5) Durchlauf: Die Zahl 2 wird mit 1 verglichen und vertauscht, mit 10, 8, 5, 3 muss nichtmehr verglichen werden.
Ende, die Zahl 1 muss nichtmehr verglichen werden.

Vergleichen und vertauschen betrachten wir nun als eine Operation.

1) Durchlauf -> 5 Operationen
2) Durchlauf -> 4 Operationen
3) Durchlauf -> 3 Operationen
4) Durchlauf -> 2 Operationen
5) Durchlauf -> 1 Operation

Das sind für ein Array der Länge 6, 15 Operationen.

Die allgemeine Formel lautet

1) (n-1) + (n-2) + ... 1
2) Das ist ja der kleine Gauß minus n: (n * (n + 1))/2 - n
3) (n² + n - 2*n)/2
4) (n² - n)/2
5) 1/2*(n² - n)
6) n² - n -> Konstante Werte werden bei der O - Notation entfernt
7) n² -> n ist zu n² vernachlässigbar und wird entfernt

Laufzeit

Somit ist die Laufzeit von Bubblesort O(n²)

Laufzeit Bestcase

Liegt bereits eine sortierte Liste vor, so benötigt Bubblesort nur einen Durchlauf. Dabei erfolgen n - 1 vergleiche. Die Konstante wird entfernt.
Die Laufzeit im Bestcase ist O(n)

Algorithmen und Datenstrukturen

Inhaltsverzeichnis

Landau Symbole oder O - Notation

Datenstrukturen

Array

Vorteile

Nachteile

Einsatzgebiete

Liste

ArrayList

Vorteile

Nachteile

Code beispiel

Einsatzgebiete

LinkedList oder verkettete Liste

Vorteile

Nachteile

Einsatzgebiete

Code beispiel

Assoziatives Array

Sortieralgorithmen

Eigenschaften

In-Place

Stabil

Bubblesort

Code

Laufzeitanalyse

Die allgemeine Formel lautet

Laufzeit

Laufzeit Bestcase

Navigationsmenü

Algorithmen und Datenstrukturen

Landau Symbole oder O - Notation

Datenstrukturen

Array

Vorteile

Nachteile

Einsatzgebiete

Liste

ArrayList

Vorteile

Nachteile

Code beispiel

Einsatzgebiete

LinkedList oder verkettete Liste

Vorteile

Nachteile

Einsatzgebiete

Code beispiel

Assoziatives Array

Sortieralgorithmen

Eigenschaften

In-Place

Stabil

Bubblesort

Code

Laufzeitanalyse

Die allgemeine Formel lautet

Laufzeit

Laufzeit Bestcase

Navigationsmenü

Suche