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. Um das Grenzverhalten eines Algorithmus zu betrachten, analysieren wir wieviele Operationen im schlechtesten Fall im bezug auf die größe des Problems (z.B.: Anzahl der Elemente) benötigt werden. Konstante Werte können dabei vernachlässigt werden.

Beispiel

Suchen des kleinsten und größten Elements in einem Array.

1

2

3

4

5

6

Um das größte Element zu finden, werden 5 Schritte benötigt, dies entspricht der Länge des Arrays - 1. Für die Suche des größten Elements benötigen wir ebenfalls 5 Schritte. Somit ist die Laufzeit für unseren Algorithmus 2 * (n - 1), die Konstanten werden entfernt: O(n)

public void findMinAndMax(int[] arr) {
  int min = arr[0];
  int max = arr[0];
  for(int i=1; i<arr.length; i++) {
    min = Math.min(min, arr[i]);
  }
  for(int i=1; i<arr.length; i++) {
    max = Math.max(max, arr[i]);
  }
  System.out.println("Min: "+min);
  System.out.println("Max: "+max);
}

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:

• 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.

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

• 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.

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

Vorteile

• Einfügen und Löschen effizient - Es müssen lediglich die Zeiger auf den Vorgänger/Nachfolger geändert werden.
• Speicherbedarf flexibel - Der Speicherbedarf wächst und schrumpft mit der Anzahl der Elemente.

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 int get(int index) {
  Node current = root;
  for(int i=0; i<index && current != null; i++) {
    current = current.next();
  }
  if(current == null) {
    throw new IndexOutOfBoundsException();
  }
  return current.getValue();
}

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.

Bäume

Bäume sind Datenstrukturen, welche im Kontext von Suchstrukturen, automatisch einer gewissen Ordnung folgen. Bereits nach dem Einfügen sind diese Element sortiert.
Es gibt eine Vielzahl verschiedener Baumstrukturen, die sich in einigen Punkten unterscheiden:

• Binärbaum oder Binärer Suchbaum
• AVL Baum
• Rot schwarz baum
• B*Baum
• ...

Elemente eines Baums

Betrachten wir die folgende Grafik, so können wir die Elemente leicht identifizieren. Weiters ist zu beachten, Bäume in der Informatik werden meist mit der Wurzel ganz oben dargestellt, nicht wie im echten Leben. Weiters wächst auch der Baum nach unten.

Elemente eines Baums. Quelle: https://de.wikipedia.org/wiki/Rot-Schwarz-Baum

• Wurzel - Das erste Element im Baum
• Blatt oder äußerer Knoten - Knoten ganz außen ohne Nachkommen
• Innerer Knoten - Knoten dazwischen

Eigenschaften eines Baums

Höhe eines Baumes

Die höhe des Baumes ist die maximal auftretende Tiefe, also wieviele Element wächst der Baum nach unten. Somit hätte ein Baum mit nur einer Wurzel die Höhe von 0, das heißt er wächst 0 ebenen nach unten. In der Graphentheorie, ist eine Zuordnung der Höhe, nur auf nichtleere Bäume definiert. Teilweise wird die Höhe auch um 1 erhöht, damit ein leerer Baum die Höhe 0 hat und ein Baum mit nur einer Wurzel 1. Das soll uns aber jetzt nicht weiter beschäftigen.
Folgende Grafik illustriert wie die Höhe eines Baumes bestimmt wird. Man beachte: Minimale Anzahl Knoten trifft hier nur auf balancierte bäume zu.

Höhe eines Baumes bestimmen. Quelle: https://www1.pub.informatik.uni-wuerzburg.de/databases/Binaere_Suchbaeume/avl_trees/properties/height.html

Balance

Ob ein Binärer Suchbaum balanciert ist oder nicht, ist entscheidend für die Laufzeit der binären Suche.

Ein Baum ist balanciert wenn sich die Höhe aller Teilbäume nicht mehr als um einen gewissen Wert unterscheidet. Bei z.b.: AVL Bäumen darf die Höhendifferenz maximal 1 betragen, dies können wir auch für den Binärbaum annehmen

Um die Balance zu bestimmen, müssen wir alle Teilbäume betrachten, wir gehen den Baum von unten nach oben durch und schreiben zu jedem Knoten die Differenz der Höhe des linken und rechten Teilbaums. Folgende Grafik sollte das recht gut illustrieren:

Balance eines Baumes. Quelle: https://de.wikipedia.org/wiki/AVL-Baum

Ist ein Baum nicht balanciert, so wächst die Suche nach einem Element, je nach grad der Entwartung, bis zur Laufzeit O(n). Das bei der linearen Suche in einem Array oder einer Liste.

Entarteter Suchbaum. Quelle: https://de.wikipedia.org/wiki/Balancierter_Baum

Suche in einem Binärbaum

Das Laufzeitverhalten der Suche in einem Binärbaum entspricht immer seiner Höhe (je nach Höhendefinition + 1). Betrachten wir folgendes Beispiel:

Balance eines Baumes. Quelle: https://de.wikipedia.org/wiki/AVL-Baum

• Die Höhe des Baumes beträgt 4, somit sind 5 Operationen nötig
• Wir suchen nach U
• Die Vergleiche und die Navigation fassen wir als eine Operation zusammen
• Vergleich mit J, P, V, S und zu guter letzt U

Die Höhe eines balancierten Baumes können wir vereinfacht mit log₂(n) annehmen. Somit ist der Aufwand unserer Suche O(log₂(n))

Code Beispiele

Sortierte Ausgabe eines binären Suchbaums (In-Order)

public void printInOrder() {
  print(root);
}

public void printInOrder(Node node) {
  if(node == null) {
    return;
  }
  //Rekursiver Aufruf für den Linken Teilbaum
  print(node.getLeft());
  //Ausgabe des aktuellen Wertes
  System.out.print(" "+node.getValue()+" ");
  //Rekursiver Aufruf für den Linken Teilbaum
  print(node.getRight());
}

Einfügen eines Elements

public void add(int value) {
  add(root, new Node(value));
}

private void add(Node node, Node newNode) {
  if(root == null) {
    root = newNode;
    return;
  }
  if(node.getValue() < newNode.getValue()) {
    if(node.getLeft() == null) {
      node.setLeft(newNode);
    } else {
      add(node.getLeft(), newNode);
    }
  } else {
    if(node.getRight() == null) {
      node.setRight(newNode);
    } else {
      add(node.getRight(), newNode);
    }
  }
}

Finden eines Elements

public boolean contains(int value) {
  return contains(root, value);
}

private void contains(Node node, int value) {
  if(node == null) {
    return false;
  }
  if(node.getValue() == value) {
    return true;
  } else if(node.getValue() < value) {
    return contains(node.getLeft(), value);
  } else {
    return contains(node.getRight(), value);
  }
}

O Notation

Hier findet sich die O - Notation für einige gebräuchliche Operationen und dessen Erklärung. Man beachte, es muss immer vom schlechtesten Fall ausgegangen werden.

Element an bestimmtem Index holen

Datenstruktur	O - Notation	Begründung
LinkedList	O(n)	Liste muss bis zum gewünschten Index durchlaufen werden
ArrayList	O(1)	Index kann berechnet werden
Array	O(1)	Index kann berechnet werden

Element an bestimmtem Index löschen

Datenstruktur	O - Notation	Begründung
LinkedList	O(n)	Liste muss bis zum gewünschten Index durchlaufen werden, das Löschen selbst hat eine konstante Laufzeit, es müssen nur die Verknüpfungen aktualisiert werden
ArrayList	O(n)	Element kann direkt durch berechnung des Index gelöscht werden, jedoch müssen alle Nachfolgenden Elemente nach links verschoben werden
Array	O(n)	Element kann direkt durch berechnung des Index gelöscht werden, jedoch müssen alle Nachfolgenden Elemente nach links verschoben werden

Element an bestimmtem Index einfügen

Datenstruktur	O - Notation	Begründung
LinkedList	O(n)	Liste muss bis zum gewünschten Index durchlaufen werden, das Einfügen selbst hat eine konstante Laufzeit, ein neuer Knoten wird erstellt und die Verknüpfungen werden aktualisiert
ArrayList	O(n)	Element kann direkt durch berechnung des Index eingefügt werden, jedoch müssen alle Elemente ab diesem Index nach rechts verschoben werden
Array	O(n)	Element kann direkt durch berechnung des Index eingefügt werden, jedoch müssen alle Elemente ab diesem Index nach rechts verschoben werden

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. Folgende Grafik illustriert die Funktionsweise, man beachte dass bei jedem Durchlauf die Anzahl der Vergleiche um 1 abnimmt, da beim letzten Vergleich immer die höchste Zahl ganz rechts steht.

Funktionsweise Bubblesort. Quelle: https://de.wikipedia.org/wiki/Bubblesort

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)