Algorithmen und Datenstrukturen - Versionsgeschichte

Drlue: /* Laufzeitanalyse */

2021-02-10T09:35:00Z

Laufzeitanalyse

← Nächstältere Version		Version vom 10. Februar 2021, 09:35 Uhr
Zeile 446:		Zeile 446:

	=== Laufzeitanalyse ===		=== Laufzeitanalyse ===
	Für die Laufzeitanalyse verwenden wir die maximal mögliche Laufzeit.		Für die Laufzeitanalyse verwenden wir die '''maximal''' mögliche '''Laufzeit'''.
	Betrachten wir hierfür folgendes Array:		Betrachten wir hierfür folgendes Array:
	10,8,5,3,2,1		10,8,5,3,2,1
	* 1) Durchlauf: Die Zahl 10 wird mit 8,5,3,2 und 1 verglichen und vertauscht.		* 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'''.		* 2) Durchlauf: Die Zahl 8 wird mit 5,3,2 und 1 verglichen und vertauscht, '''mit 10 muss nicht mehr verglichen werden'''.
	* 3) Durchlauf: Die Zahl 5 wird mit 3,2 und 1 verglichen und vertauscht, '''mit 10, 8 muss ~~nichtmehr~~ verglichen werden'''.		* 3) Durchlauf: Die Zahl 5 wird mit 3,2 und 1 verglichen und vertauscht, '''mit 10, 8 muss nicht mehr verglichen werden'''.
	* 4) Durchlauf: Die Zahl 3 wird mit 2 und 1 verglichen und vertauscht, '''mit 10, 8, 5 muss ~~nichtmehr~~ verglichen werden'''.		* 4) Durchlauf: Die Zahl 3 wird mit 2 und 1 verglichen und vertauscht, '''mit 10, 8, 5 muss nicht mehr verglichen werden'''.
	* 5) Durchlauf: Die Zahl 2 wird mit 1 verglichen und vertauscht, '''mit 10, 8, 5, 3 muss ~~nichtmehr~~ verglichen werden'''.		* 5) Durchlauf: Die Zahl 2 wird mit 1 verglichen und vertauscht, '''mit 10, 8, 5, 3 muss nicht mehr verglichen werden'''.
	* Ende, die Zahl 1 muss ~~nichtmehr~~ verglichen werden.		* Ende, die Zahl 1 muss nicht mehr verglichen werden.

	Vergleichen und ~~vertauschen~~ betrachten wir nun als eine Operation.		Vergleichen und Vertauschen betrachten wir nun als eine Operation (da Konstant).

	* 1) Durchlauf -> 5 Operationen		* 1) Durchlauf -> 5 Operationen
Zeile 477:		Zeile 477:

	==== Laufzeit ====		==== Laufzeit ====
	'''Somit ist die Laufzeit von Bubblesort O(n<sup>2</sup>)'''		'''Somit ist die Laufzeit von '''Bubblesort''' O(n<sup>2</sup>)'''
	==== Laufzeit Bestcase ====		==== Laufzeit Bestcase ====
	Liegt bereits eine sortierte Liste vor, so benötigt Bubblesort nur einen Durchlauf. Dabei erfolgen '''n - 1''' vergleiche. Die Konstante wird entfernt.		Liegt bereits eine sortierte Liste vor, so benötigt '''Bubblesort''' nur einen Durchlauf. Dabei erfolgen '''n - 1''' vergleiche. Die Konstante wird entfernt.
	<br>		<br>
	'''Die Laufzeit im Bestcase ist O(n)'''		'''Die Laufzeit im Bestcase ist O(n)'''

Drlue: /* Code */

2021-02-10T09:33:37Z

Code

← Nächstältere Version		Version vom 10. Februar 2021, 09:33 Uhr
Zeile 409:		Zeile 409:

	=== Code ===		=== Code ===
	Bubblesort in Java		Folgendes Code Beispiel zeigt die Implementierung von '''Bubblesort''' in '''Java''':
	{{JML\|code=		{{JML\|code=
	public class Bubblesort {		public class Bubblesort {

Drlue: /* Code */

2021-02-10T09:32:47Z

Code

← Nächstältere Version		Version vom 10. Februar 2021, 09:32 Uhr
Zeile 412:		Zeile 412:
	{{JML\|code=		{{JML\|code=
	public class Bubblesort {		public class Bubblesort {
	public static void sort(int[] arr) {		public static void sort(int[] arr) {
	int operations = 0;		int operations = 0;
	int n = arr.length;		int n = arr.length;
	boolean swapped = false;		boolean swapped = false;
	do {		do {
	swapped = false;		swapped = false;
	for (int i = 0; i < n - 1; i++) {		for (int i = 0; i < n - 1; i++) {
	operations++;		operations++;
	if (arr[i] > arr[i + 1]) {		if (arr[i] > arr[i + 1]) {
	int tmp = arr[i];		int tmp = arr[i];
	arr[i] = arr[i + 1];		arr[i] = arr[i + 1];
	arr[i + 1] = tmp;		arr[i + 1] = tmp;
	swapped = true;		swapped = true;
	}		}
	}		}
	// Letztes Element ist an der richtigen stelle, n um 1 reduzieren		// Letztes Element ist an der richtigen stelle, n um 1 reduzieren
	n = n - 1;		n = n - 1;
	} while (swapped);		} while (swapped);
	System.out.println("Operations: " + operations);		System.out.println("Operations: " + operations);
	}		}

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

Drlue: /* Sortieralgorithmen */

2021-02-10T09:32:25Z

Sortieralgorithmen

← Nächstältere Version		Version vom 10. Februar 2021, 09:32 Uhr
Zeile 395:		Zeile 395:

	= Sortieralgorithmen =		= 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.		'''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 ==		== Eigenschaften ==
	Sortieralgorithmen können über mehrere Eigenschaften verfügen.		'''Sortieralgorithmen''' können über mehrere '''Eigenschaften''' verfügen.
	=== In-Place ===		=== 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.		Das bedeutet der '''Sortieralgorithmus''' benötigt '''keinen''' weiteren Speicherplatz, oder der Speicherbedarf ist '''konstant''' und nicht von der Anzahl der Elemente abhängig. Z.b. der Sortieralgorithmus Mergesort teilt die Daten der bestehenden Liste in Sublisten auf, er ist somit nicht In-Place.
	=== Stabil ===		=== Stabil ===
	Ein Sortieralgorithmus arbeitet stabil, wenn dieser eine bestehende korrekte Ordnung nicht verändert.		Ein '''Sortieralgorithmus''' arbeitet '''stabil''', wenn dieser eine bestehende korrekte Ordnung '''nicht''' verändert.

	== Bubblesort ==		== 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. ~~'''~~Weiters kann die Sortierung abgebrochen werden, wenn in einem Durchlauf keine Zahl vertauscht wurde.~~'''~~		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. Weiters kann die Sortierung abgebrochen werden, wenn in einem Durchlauf keine Zahl vertauscht wurde.
	[[Datei:Bubble-sort-example-300px.gif\|mini\|none\|Funktionsweise Bubblesort. ~~Quelle:~~ https://de.wikipedia.org/wiki/Bubblesort]]		[[Datei:Bubble-sort-example-300px.gif\|mini\|none\|Funktionsweise Bubblesort. <ref>https://de.wikipedia.org/wiki/Bubblesort</ref>]]

	=== Code ===		=== Code ===

Drlue: /* O Notation */

2021-02-10T09:28:24Z

O Notation

← Nächstältere Version		Version vom 10. Februar 2021, 09:28 Uhr
Zeile 359:		Zeile 359:

	== O Notation ==		== O Notation ==
	Hier findet sich die '''O - Notation''' für einige gebräuchliche Operationen und dessen Erklärung. Man beachte, es wird hierbei immer vom schlechtesten Fall ausgegangen. Es wird auch oft die '''O - Notation''' für '''~~minimal/durchschnitt/maximal~~'''.		Hier findet sich die '''O - Notation''' für einige gebräuchliche Operationen und dessen Erklärung. Man beachte, es wird hierbei immer vom schlechtesten Fall ausgegangen. Es wird auch oft die '''O - Notation''' für die '''Minimal-, Durchschnitts-, und Maximallaufzeit''' angegeben.
	{\| class="wikitable"		{\| class="wikitable"
	\|+ Element an bestimmtem Index holen		\|+ Element an bestimmtem Index holen

Drlue: /* O Notation */

2021-02-10T09:27:47Z

O Notation

← Nächstältere Version		Version vom 10. Februar 2021, 09:27 Uhr
Zeile 359:		Zeile 359:

	== O Notation ==		== 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~~.		Hier findet sich die '''O - Notation''' für einige gebräuchliche Operationen und dessen Erklärung. Man beachte, es wird hierbei immer vom schlechtesten Fall ausgegangen. Es wird auch oft die '''O - Notation''' für '''minimal/durchschnitt/maximal'''.
	{\| class="wikitable"		{\| class="wikitable"
	\|+ Element an bestimmtem Index holen		\|+ Element an bestimmtem Index holen
Zeile 378:		Zeile 378:
	\| 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		\| 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		\| 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		\| Array \|\| O(n) \|\| Element kann direkt durch Berechnung des Index gelöscht werden, jedoch müssen alle nachfolgenden Elemente nach links verschoben werden
	\|}		\|}
	{\| class="wikitable"		{\| class="wikitable"
Zeile 389:		Zeile 389:
	\| 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		\| 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		\| 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		\| 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
	\|}		\|}

Drlue: /* Code Beispiele */

2021-02-10T09:24:32Z

Code Beispiele

← Nächstältere Version		Version vom 10. Februar 2021, 09:24 Uhr
Zeile 257:		Zeile 257:

	=== Code Beispiele ===		=== Code Beispiele ===
	~~Sortierte Ausgabe eines binären Suchbaums '''(In-Order)'''~~
	{{JML\|code=		{{JML\|code=
	public void ~~printInOrder~~() {
	~~print~~(~~root~~);		//Datenstruktur für die Knoten
			public class Node {
			private Node left;
			private Node right;
			private int value;

			public Node(int value) {
			this.value = value;
			}

			public Node getLeft() {
			return this.left;
			}

			public Node getRight() {
			return this.right;
			}

			public void setLeft(Node node) {
			this.left = node;
			}

			public void setRight(Node node) {
			this.right = node;
			}

			public int getValue() {
			return this.value;
			}
	}		}

	public ~~void printInOrder~~(~~Node node~~) {		//Implementierung des Baumes selbst
	if(~~node == null~~) {		public class MyTree {
	~~return~~;		//Referenz auf die Wurzel
			private Node root;

			//Sortierte Ausgabe eines binären Suchbaums (In-Order)
			public void printInOrder() {
			print(root);
	}		}
	~~//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~~		private void printInOrder(Node node) {
	{~~{JML\|code=~~		if(node == null) {
	~~public void add~~(~~int value~~) {		return;
	~~add~~(~~root, new Node~~(~~value~~));		}
	}		//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());
			}

	~~private~~ void add(~~Node node, Node newNode~~) {		//Einfügen eines Elements
	if(root ~~== null~~) {		public void add(int value) {
	~~root = newNode;~~		add(root, new Node(value));
	~~return~~;
	}		}
	if(node~~.getValue() <~~ newNode~~.getValue()~~) {
	if(~~node.getLeft()~~ == null) {		private void add(Node node, Node newNode) {
	~~node.setLeft(~~newNode);		if(root == null) {
	~~} else {~~		root = newNode;
	~~add(node.getLeft(), newNode)~~;		return;
	}		}
	~~} else~~ {		if(node.getValue() < newNode.getValue()) {
	if(node.~~getRight~~() == null) {		if(node.getLeft() == null) {
	node.~~setRight~~(newNode);		node.setLeft(newNode);
			} else {
			add(node.getLeft(), newNode);
			}
	} else {		} else {
	add(node.getRight(), newNode);		if(node.getRight() == null) {
			node.setRight(newNode);
			} else {
			add(node.getRight(), newNode);
			}
	}		}
	}		}
	}
	}}

	Finden eines Elements		//Finden eines Elements
	~~{{JML\|code=~~		public boolean contains(int value) {
	public boolean contains(int value) {		return contains(root, value);
	return contains(root, value);		}
	}

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

Drlue: /* Code Beispiel */

2021-02-10T09:19:40Z

Code Beispiel

← Nächstältere Version		Version vom 10. Februar 2021, 09:19 Uhr
Zeile 155:		Zeile 155:
	//Die Implementierung der LinkedList		//Die Implementierung der LinkedList
	public class MyList {		public class MyList {
			//Referenz für erstes Listenelement
	private Node root;		private Node root;

	//Hinzufügen eines Elements		//Hinzufügen eines Elements
	public boolean add(Integer element) {		public boolean add(Integer element) {

Drlue: /* Code Beispiel */

2021-02-10T09:19:06Z

Code Beispiel

← Nächstältere Version		Version vom 10. Februar 2021, 09:19 Uhr
Zeile 130:		Zeile 130:

	==== Code Beispiel ====		==== Code Beispiel ====
	~~Datenstruktur Node selbst:~~
	{{JML\|code=		{{JML\|code=
			//Datenstruktur Node
	public class Node {		public class Node {
	private Integer value;		private Integer value;
Zeile 152:		Zeile 152:
	}		}
	}		}
	}}
	''Hinzufügen eines Elements''		//Die Implementierung der LinkedList
	~~{{JML\|code=~~		public class MyList {
	public boolean add(Integer element) {		private Node root;
	Node newNode = new Node(element);		//Hinzufügen eines Elements
	if(root == null) {		public boolean add(Integer element) {
	root = newNode;		Node newNode = new Node(element);
	} ~~else~~ {		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;		Node current = root;
	~~while~~(current~~.next()~~ != null) {		for(int i=0; i<index && current != null; i++) {
	current = current.next();		current = current.next();
	}		}
	~~current.setNext~~(~~newNode);~~		if(current == null) {
	}		throw new IndexOutOfBoundsException();
	~~return true;~~		}
	}		return current.getValue();
	}}

	~~''Holen eines Elements''~~
	~~{{JML\|code=~~
	~~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();~~
	}		}
	}}		}}

Drlue: /* Suche in einem Binärbaum */

2021-02-10T09:15:50Z

Suche in einem Binärbaum

← Nächstältere Version		Version vom 10. Februar 2021, 09:15 Uhr
Zeile 244:		Zeile 244:

	=== Suche in einem Binärbaum ===		=== 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:		Das '''Laufzeitverhalten''' der '''Suche''' in einem '''Binärbaum''' entspricht immer seiner Höhe (je nach Höhendefinition + 1). Betrachten wir folgendes Beispiel:
	[[Datei:AVL-tree-wBalance K.svg.png\|300px\|none\|Balance eines Baumes. Quelle: https://de.wikipedia.org/wiki/AVL-Baum]]		[[Datei:AVL-tree-wBalance K.svg.png\|300px\|none\|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		* Die Höhe des Baumes beträgt 4, somit sind 5 Operationen nötig
	* Wir suchen nach ''U''		* Wir suchen nach ''U''
	* Die Vergleiche und die Navigation fassen wir als eine Operation zusammen		* Die Vergleiche und die Navigation fassen wir als eine Operation zusammen (die Konstante streichen wir direkt)
	* Vergleich mit ''J'', ''P'', ''V'', ''S'' und zu guter letzt ''U''		* Vergleich mit ''J'', ''P'', ''V'', ''S'' und zu guter letzt ''U''
	<br>		<br>
	Die Höhe eines balancierten Baumes können wir vereinfacht mit '''log<sub>2</sub>(n)''' annehmen. Somit ist der Aufwand unserer Suche '''O(log<sub>2</sub>(n))'''		Die '''Höhe''' eines '''balancierten Baumes''' können wir vereinfacht mit '''log<sub>2</sub>(n)''' annehmen. Somit ist der Aufwand unserer Suche '''O(log<sub>2</sub>(n))'''

	=== Code Beispiele ===		=== Code Beispiele ===