Algorithmen Grundlagen: Komplexitätsanalyse, Big-O-Notation, Such- & Sortieralgorithmen
Dieser Beitrag ist eine umfassende Einführung in die Algorithmen Grundlagen – inklusive Komplexitätsanalyse, Big-O-Notation, Suchalgorithmen und Sortieralgorithmen mit praktischen Beispielen.
In a Nutshell
Algorithmen sind schrittweise Anweisungen zur Problemlösung. Big-O-Notation beschreibt ihre Komplexität, Suchalgorithmen finden Elemente, Sortieralgorithmen ordnen Daten.
Kompakte Fachbeschreibung
Algorithmen sind wohldefinierte, endliche Anweisungsfolgen zur Lösung eines Problems. Sie sind die Grundlage der Informatik und Softwareentwicklung.
Komplexitätsanalyse:
- Zeitkomplexität: Anzahl der Operationen als Funktion der Eingabegröße
- Speicherkomplexität: Benötigter Speicherplatz
- Big-O-Notation: Obere Schranke der Komplexität
- Best/Average/Worst Case: Verschiedene Laufzeitszenarien
Big-O-Notation (wichtigste):
- O(1): Konstante Zeit
- O(log n): Logarithmische Zeit
- O(n): Lineare Zeit
- O(n log n): Linearithmische Zeit
- O(n²): Quadratische Zeit
- O(2ⁿ): Exponentielle Zeit
Prüfungsrelevante Stichpunkte
- Algorithmen: Wohldefinierte Anweisungsfolgen zur Problemlösung
- Big-O-Notation: Mathematische Beschreibung der Komplexität
- Zeitkomplexität: Anzahl der Operationen abhängig von Eingabegröße
- Suchalgorithmen: Linear Search (O(n)), Binary Search (O(log n))
- Sortieralgorithmen: Bubble Sort (O(n²)), Quick Sort (O(n log n))
- Best/Worst/Average Case: Verschiedene Laufzeitszenarien
- IHK-relevant: Grundlage für effiziente Softwareentwicklung
Kernkomponenten
- Algorithmus-Konzept: Eingabe, Verarbeitung, Ausgabe
- Komplexitätsanalyse: Zeit- und Speicherplatzbedarf
- Big-O-Notation: Asymptotische Analyse
- Suchalgorithmen: Lineare und binäre Suche
- Sortieralgorithmen: Verschiedene Sortierstrategien
- Datenstrukturen: Arrays, Listen, Bäume, Graphen
- Rekursion: Selbstaufrufende Algorithmen
- Divide and Conquer: Problemlösung durch Teilung
Praxisbeispiele
1. Big-O-Notation und Komplexitätsanalyse
import java.util.*;
public class Komplexitaetsanalyse {
// O(1) - Konstante Zeit
public int getFirstElement(int[] array) {
if (array.length == 0) {
throw new IllegalArgumentException("Array ist leer");
}
return array[0]; // Immer eine Operation
}
// O(n) - Lineare Zeit
public int findMax(int[] array) {
if (array.length == 0) {
throw new IllegalArgumentException("Array ist leer");
}
int max = array[0];
for (int i = 1; i < array.length; i++) { // n Operationen
if (array[i] > max) {
max = array[i];
}
}
return max;
}
// O(n²) - Quadratische Zeit
public void printPairs(int[] array) {
for (int i = 0; i < array.length; i++) { // n Schleifen
for (int j = 0; j < array.length; j++) { // n Schleifen
System.out.println(array[i] + ", " + array[j]);
}
}
// Gesamt: n * n = n² Operationen
}
// O(log n) - Logarithmische Zeit
public int powerOfTwo(int n) {
int result = 1;
while (n > 0) { // log₂(n) Schleifendurchläufe
result *= 2;
n /= 2;
}
return result;
}
// O(n log n) - Linearithmische Zeit
public void mergeSort(int[] array) {
if (array.length <= 1) {
return;
}
int mid = array.length / 2;
int[] left = Arrays.copyOfRange(array, 0, mid);
int[] right = Arrays.copyOfRange(array, mid, array.length);
mergeSort(left); // O(log n) Rekursionstiefe
mergeSort(right);
merge(array, left, right); // O(n) für jeden Merge
}
private void merge(int[] result, int[] left, int[] right) {
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result[k++] = left[i++];
} else {
result[k++] = right[j++];
}
}
while (i < left.length) {
result[k++] = left[i++];
}
while (j < right.length) {
result[k++] = right[j++];
}
}
// O(2ⁿ) - Exponentielle Zeit
public int fibonacci(int n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2); // 2ⁿ Aufrufe
}
// Komplexitätsanalyse mit Zeitmessung
public void analyzeComplexity() {
int[] sizes = {100, 1000, 10000, 100000};
System.out.println("=== Komplexitätsanalyse ===");
System.out.println("Größe\tO(1)\tO(n)\tO(n²)\tO(log n)");
for (int size : sizes) {
int[] array = new int[size];
// Array mit Zufallszahlen füllen
Random random = new Random();
for (int i = 0; i < size; i++) {
array[i] = random.nextInt(1000);
}
// O(1) messen
long start = System.nanoTime();
getFirstElement(array);
long o1Time = System.nanoTime() - start;
// O(n) messen
start = System.nanoTime();
findMax(array);
long onTime = System.nanoTime() - start;
// O(n²) messen (nur für kleine Arrays)
long on2Time = 0;
if (size <= 1000) {
start = System.nanoTime();
printPairs(array);
on2Time = System.nanoTime() - start;
}
// O(log n) messen
start = System.nanoTime();
powerOfTwo(size);
double olognTime = System.nanoTime() - start;
System.out.printf("%d\t%d\t%d\t%d\t%.0f%n",
size, o1Time, onTime, on2Time, olognTime);
}
}
public static void main(String[] args) {
Komplexitaetsanalyse analyse = new Komplexitaetsanalyse();
// Komplexitätsanalyse
analyse.analyzeComplexity();
// Big-O Demonstration
System.out.println("\n=== Big-O Demonstration ===");
demonstrateBigO();
// Rekursion vs Iteration
System.out.println("\n=== Rekursion vs Iteration ===");
compareRecursionIteration();
}
private static void demonstrateBigO() {
int n = 1000;
Komplexitaetsanalyse demo = new Komplexitaetsanalyse();
System.out.println("Demonstration mit n = " + n);
// O(1) Beispiel
int[] array = {1, 2, 3, 4, 5};
System.out.println("O(1) - Erstes Element: " + demo.getFirstElement(array));
// O(n) Beispiel
int[] largeArray = new int[n];
for (int i = 0; i < n; i++) {
largeArray[i] = i;
}
System.out.println("O(n) - Maximum: " + demo.findMax(largeArray));
// O(log n) Beispiel
System.out.println("O(log n) - 2^" + n + " = " + demo.powerOfTwo(n));
// O(n log n) Beispiel
int[] sortArray = new int[100];
Random random = new Random();
for (int i = 0; i < 100; i++) {
sortArray[i] = random.nextInt(1000);
}
System.out.println("O(n log n) - Merge Sort durchgeführt");
demo.mergeSort(sortArray);
// O(n²) Beispiel (kleines Array)
int[] smallArray = {1, 2, 3, 4, 5};
System.out.println("O(n²) - Alle Paare:");
demo.printPairs(smallArray);
}
private static void compareRecursionIteration() {
Komplexitaetsanalyse demo = new Komplexitaetsanalyse();
int n = 30;
System.out.println("Fibonacci n = " + n);
// Rekursive Version (exponentiell)
long start = System.nanoTime();
int recursiveResult = demo.fibonacci(n);
long recursiveTime = System.nanoTime() - start;
// Iterative Version (linear)
start = System.nanoTime();
int iterativeResult = fibonacciIterative(n);
long iterativeTime = System.nanoTime() - start;
System.out.println("Rekursiv: " + recursiveResult + " (" + recursiveTime + "ns)");
System.out.println("Iterativ: " + iterativeResult + " (" + iterativeTime + "ns)");
System.out.println("Speedup: " + (recursiveTime / iterativeTime) + "x");
}
private static int fibonacciIterative(int n) {
if (n <= 1) return n;
int a = 0, b = 1;
for (int i = 2; i <= n; i++) {
int temp = a + b;
a = b;
b = temp;
}
return b;
}
}2. Suchalgorithmen
import java.util.*;
public class Suchalgorithmen {
// Lineare Suche - O(n)
public static int linearSearch(int[] array, int target) {
for (int i = 0; i < array.length; i++) {
if (array[i] == target) {
return i; // Element gefunden
}
}
return -1; // Element nicht gefunden
}
// Binäre Suche - O(log n) - Array muss sortiert sein
public static int binarySearch(int[] sortedArray, int target) {
int left = 0;
int right = sortedArray.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (sortedArray[mid] == target) {
return mid; // Element gefunden
} else if (sortedArray[mid] < target) {
left = mid + 1; // Rechts weitersuchen
} else {
right = mid - 1; // Links weitersuchen
}
}
return -1; // Element nicht gefunden
}
// Interpolationssuche - O(log log n) im Durchschnitt
// Funktioniert nur für gleichmäßig verteilte, sortierte Arrays
public static int interpolationSearch(int[] sortedArray, int target) {
int left = 0;
int right = sortedArray.length - 1;
while (left <= right && target >= sortedArray[left] && target <= sortedArray[right]) {
if (left == right) {
return sortedArray[left] == target ? left : -1;
}
// Interpolationsformel
int pos = left + ((target - sortedArray[left]) * (right - left)) /
(sortedArray[right] - sortedArray[left]);
if (sortedArray[pos] == target) {
return pos;
} else if (sortedArray[pos] < target) {
left = pos + 1;
} else {
right = pos - 1;
}
}
return -1;
}
// Exponentielle Suche - O(log n) für unendlich große Arrays
public static int exponentialSearch(int[] sortedArray, int target) {
int n = sortedArray.length;
if (sortedArray[0] == target) {
return 0;
}
// Bereich finden, in dem das Element sein könnte
int i = 1;
while (i < n && sortedArray[i] <= target) {
i = i * 2;
}
// Binäre Suche im gefundenen Bereich
return binarySearchRange(sortedArray, i / 2, Math.min(i, n - 1), target);
}
private static int binarySearchRange(int[] array, int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (array[mid] == target) {
return mid;
} else if (array[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
// Jump Search - O(√n) für sortierte Arrays
public static int jumpSearch(int[] sortedArray, int target) {
int n = sortedArray.length;
int step = (int) Math.sqrt(n);
int prev = 0;
// Block finden, in dem das Element sein könnte
while (sortedArray[Math.min(step, n) - 1] < target) {
prev = step;
step += (int) Math.sqrt(n);
if (prev >= n) {
return -1;
}
}
// Lineare Suche im Block
while (sortedArray[prev] < target) {
prev++;
if (prev == Math.min(step, n)) {
return -1;
}
}
if (sortedArray[prev] == target) {
return prev;
}
return -1;
}
// Performance-Vergleich der Suchalgorithmen
public static void compareSearchAlgorithms() {
Random random = new Random();
int[] sizes = {1000, 10000, 100000, 1000000};
System.out.println("=== Suchalgorithmen Performance-Vergleich ===");
System.out.println("Größe\tLinear\tBinär\tInterpolation\tJump\tExponential");
for (int size : sizes) {
int[] array = new int[size];
// Sortiertes Array erstellen
for (int i = 0; i < size; i++) {
array[i] = i;
}
// Zufälliges Ziel auswählen
int target = random.nextInt(size);
// Lineare Suche
long start = System.nanoTime();
int linearResult = linearSearch(array, target);
long linearTime = System.nanoTime() - start;
// Binäre Suche
start = System.nanoTime();
int binaryResult = binarySearch(array, target);
long binaryTime = System.nanoTime() - start;
// Interpolationssuche
start = System.nanoTime();
int interpolationResult = interpolationSearch(array, target);
long interpolationTime = System.nanoTime() - start;
// Jump Search
start = System.nanoTime();
int jumpResult = jumpSearch(array, target);
long jumpTime = System.nanoTime() - start;
// Exponentielle Suche
start = System.nanoTime();
int exponentialResult = exponentialSearch(array, target);
long exponentialTime = System.nanoTime() - start;
System.out.printf("%d\t%d\t%d\t%d\t\t%d\t%d%n",
size, linearTime, binaryTime, interpolationTime, jumpTime, exponentialTime);
// Ergebnisse überprüfen
assert linearResult == target;
assert binaryResult == target;
assert interpolationResult == target;
assert jumpResult == target;
assert exponentialResult == target;
}
}
public static void main(String[] args) {
// Test-Arrays erstellen
int[] unsortedArray = {64, 34, 25, 12, 22, 11, 90, 88, 76, 50, 42};
int[] sortedArray = {11, 12, 22, 25, 34, 42, 50, 64, 76, 88, 90};
System.out.println("=== Suchalgorithmen Demo ===");
// Lineare Suche
int target = 25;
int index = linearSearch(unsortedArray, target);
System.out.println("Lineare Suche: " + target + " gefunden an Index " + index);
// Binäre Suche
index = binarySearch(sortedArray, target);
System.out.println("Binäre Suche: " + target + " gefunden an Index " + index);
// Interpolationssuche
index = interpolationSearch(sortedArray, 76);
System.out.println("Interpolationssuche: 76 gefunden an Index " + index);
// Jump Search
index = jumpSearch(sortedArray, 42);
System.out.println("Jump Search: 42 gefunden an Index " + index);
// Exponentielle Suche
index = exponentialSearch(sortedArray, 88);
System.out.println("Exponentielle Suche: 88 gefunden an Index " + index);
// Performance-Vergleich
compareSearchAlgorithms();
// Suchalgorithmen-Eigenschaften
printSearchAlgorithmProperties();
}
private static void printSearchAlgorithmProperties() {
System.out.println("\n=== Suchalgorithmen Eigenschaften ===");
String[][] algorithms = {
{"Lineare Suche", "O(n)", "Unsortiert", "Einfach"},
{"Binäre Suche", "O(log n)", "Sortiert", "Effizient"},
{"Interpolationssuche", "O(log log n)", "Sortiert, gleichverteilt", "Sehr effizient"},
{"Jump Search", "O(√n)", "Sortiert", "Gut für große Arrays"},
{"Exponentielle Suche", "O(log n)", "Sortiert", "Unendliche Arrays"}
};
System.out.println("Algorithmus\t\tZeitkomplexität\tVoraussetzung\t\tBeschreibung");
System.out.println("---------\t\t--------------\t--------------\t\t-----------");
for (String[] algo : algorithms) {
System.out.printf("%-20s\t%-15s\t%-20s\t%s%n", algo[0], algo[1], algo[2], algo[3]);
}
}
}3. Sortieralgorithmen
import java.util.*;
public class Sortieralgorithmen {
// Bubble Sort - O(n²)
public static void bubbleSort(int[] array) {
int n = array.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (array[j] > array[j + 1]) {
// Elemente tauschen
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
swapped = true;
}
}
// Wenn keine Vertauschungen stattfanden, ist das Array sortiert
if (!swapped) {
break;
}
}
}
// Selection Sort - O(n²)
public static void selectionSort(int[] array) {
int n = array.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
// Minimum im unsortierten Teil finden
for (int j = i + 1; j < n; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
// Minimum mit dem aktuellen Element tauschen
if (minIndex != i) {
int temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
}
}
// Insertion Sort - O(n²) worst case, O(n) best case
public static void insertionSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int key = array[i];
int j = i - 1;
// Elemente verschieben, bis die richtige Position gefunden ist
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = key;
}
}
// Quick Sort - O(n log n) average, O(n²) worst case
public static void quickSort(int[] array) {
quickSortRecursive(array, 0, array.length - 1);
}
private static void quickSortRecursive(int[] array, int low, int high) {
if (low < high) {
int pivotIndex = partition(array, low, high);
quickSortRecursive(array, low, pivotIndex - 1);
quickSortRecursive(array, pivotIndex + 1, high);
}
}
private static int partition(int[] array, int low, int high) {
int pivot = array[high]; // Letztes Element als Pivot
int i = (low - 1); // Index des kleineren Elements
for (int j = low; j < high; j++) {
if (array[j] < pivot) {
i++;
swap(array, i, j);
}
}
swap(array, i + 1, high);
return i + 1;
}
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
// Merge Sort - O(n log n)
public static void mergeSort(int[] array) {
if (array.length <= 1) {
return;
}
int mid = array.length / 2;
int[] left = Arrays.copyOfRange(array, 0, mid);
int[] right = Arrays.copyOfRange(array, mid, array.length);
mergeSort(left);
mergeSort(right);
merge(array, left, right);
}
private static void merge(int[] result, int[] left, int[] right) {
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result[k++] = left[i++];
} else {
result[k++] = right[j++];
}
}
while (i < left.length) {
result[k++] = left[i++];
}
while (j < right.length) {
result[k++] = right[j++];
}
}
// Heap Sort - O(n log n)
public static void heapSort(int[] array) {
int n = array.length;
// Max-Heap bauen
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(array, n, i);
}
// Elemente aus dem Heap extrahieren
for (int i = n - 1; i > 0; i--) {
swap(array, 0, i);
heapify(array, i, 0);
}
}
private static void heapify(int[] array, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && array[left] > array[largest]) {
largest = left;
}
if (right < n && array[right] > array[largest]) {
largest = right;
}
if (largest != i) {
swap(array, i, largest);
heapify(array, n, largest);
}
}
// Performance-Vergleich der Sortieralgorithmen
public static void compareSortingAlgorithms() {
Random random = new Random();
int[] sizes = {1000, 5000, 10000, 20000};
System.out.println("=== Sortieralgorithmen Performance-Vergleich ===");
System.out.println("Größe\tBubble\tSelection\tInsertion\tQuick\tMerge\tHeap");
for (int size : sizes) {
// Test-Array erstellen
int[] originalArray = new int[size];
for (int i = 0; i < size; i++) {
originalArray[i] = random.nextInt(10000);
}
long[] times = new long[6];
String[] names = {"Bubble", "Selection", "Insertion", "Quick", "Merge", "Heap"};
// Bubble Sort
int[] array = originalArray.clone();
long start = System.nanoTime();
bubbleSort(array);
times[0] = System.nanoTime() - start;
// Selection Sort
array = originalArray.clone();
start = System.nanoTime();
selectionSort(array);
times[1] = System.nanoTime() - start;
// Insertion Sort
array = originalArray.clone();
start = System.nanoTime();
insertionSort(array);
times[2] = System.nanoTime() - start;
// Quick Sort
array = originalArray.clone();
start = System.nanoTime();
quickSort(array);
times[3] = System.nanoTime() - start;
// Merge Sort
array = originalArray.clone();
start = System.nanoTime();
mergeSort(array);
times[4] = System.nanoTime() - start;
// Heap Sort
array = originalArray.clone();
start = System.nanoTime();
heapSort(array);
times[5] = System.nanoTime() - start;
// Ergebnisse ausgeben
System.out.printf("%d", size);
for (long time : times) {
System.out.printf("\t%d", time);
}
System.out.println();
}
}
// Stabilitätstest
public static void testStability() {
System.out.println("\n=== Stabilitätstest ===");
// Array mit Duplikaten
int[] array = {5, 2, 8, 5, 1, 9, 3, 5};
System.out.println("Original: " + Arrays.toString(array));
// Bubble Sort (stabil)
int[] bubbleArray = array.clone();
bubbleSort(bubbleArray);
System.out.println("Bubble Sort: " + Arrays.toString(bubbleArray));
// Quick Sort (nicht stabil)
int[] quickArray = array.clone();
quickSort(quickArray);
System.out.println("Quick Sort: " + Arrays.toString(quickArray));
// Merge Sort (stabil)
int[] mergeArray = array.clone();
mergeSort(mergeArray);
System.out.println("Merge Sort: " + Arrays.toString(mergeArray));
}
public static void main(String[] args) {
// Test-Array
int[] array = {64, 34, 25, 12, 22, 11, 90, 88, 76, 50, 42};
System.out.println("=== Sortieralgorithmen Demo ===");
// Bubble Sort
int[] bubbleArray = array.clone();
bubbleSort(bubbleArray);
System.out.println("Bubble Sort: " + Arrays.toString(bubbleArray));
// Selection Sort
int[] selectionArray = array.clone();
selectionSort(selectionArray);
System.out.println("Selection Sort: " + Arrays.toString(selectionArray));
// Insertion Sort
int[] insertionArray = array.clone();
insertionSort(insertionArray);
System.out.println("Insertion Sort: " + Arrays.toString(insertionArray));
// Quick Sort
int[] quickArray = array.clone();
quickSort(quickArray);
System.out.println("Quick Sort: " + Arrays.toString(quickArray));
// Merge Sort
int[] mergeArray = array.clone();
mergeSort(mergeArray);
System.out.println("Merge Sort: " + Arrays.toString(mergeArray));
// Heap Sort
int[] heapArray = array.clone();
heapSort(heapArray);
System.out.println("Heap Sort: " + Arrays.toString(heapArray));
// Performance-Vergleich
compareSortingAlgorithms();
// Stabilitätstest
testStability();
// Sortieralgorithmen-Eigenschaften
printSortingAlgorithmProperties();
}
private static void printSortingAlgorithmProperties() {
System.out.println("\n=== Sortieralgorithmen Eigenschaften ===");
String[][] algorithms = {
{"Bubble Sort", "O(n²)", "In-place", "Stabil", "Einfach"},
{"Selection Sort", "O(n²)", "In-place", "Nicht stabil", "Einfach"},
{"Insertion Sort", "O(n²)", "In-place", "Stabil", "Kleine Arrays"},
{"Quick Sort", "O(n log n)", "In-place", "Nicht stabil", "Schnell"},
{"Merge Sort", "O(n log n)", "Out-of-place", "Stabil", "Zuverlässig"},
{"Heap Sort", "O(n log n)", "In-place", "Nicht stabil", "Garantiert"}
};
System.out.println("Algorithmus\t\tZeitkomplexität\tPlatz\t\tStabilität\tBeschreibung");
System.out.println("---------\t\t--------------\t-----\t\t---------\t-----------");
for (String[] algo : algorithms) {
System.out.printf("%-20s\t%-15s\t%-15s\t%-15s\t%s%n", algo[0], algo[1], algo[2], algo[3], algo[4]);
}
}
}
Big-O-Notation Übersicht
| Komplexität | Beschreibung | Beispiel | Wachstum |
|---|---|---|---|
| O(1) | Konstante Zeit | Array-Zugriff | 1 |
| O(log n) | Logarithmisch | Binäre Suche | log₂(n) |
| O(n) | Linear | Lineare Suche | n |
| O(n log n) | Linearithmisch | Merge Sort | n·log(n) |
| O(n²) | Quadratisch | Bubble Sort | n² |
| O(2ⁿ) | Exponentiell | Rekursive Fibonacci | 2ⁿ |
Suchalgorithmen Vergleich
| Algorithmus | Zeitkomplexität | Voraussetzung | Best Use Case |
|---|---|---|---|
| Linear Search | O(n) | Keine | Kleine, unsortierte Arrays |
| Binary Search | O(log n) | Sortiert | Große, sortierte Arrays |
| Interpolation | O(log log n) | Sortiert, gleichverteilt | Numerische Daten |
| Jump Search | O(√n) | Sortiert | Große Arrays mit Sprunggröße |
| Exponential | O(log n) | Sortiert | Unendliche Arrays |
Sortieralgorithmen Vergleich
| Algorithmus | Zeitkomplexität | Platzkomplexität | Stabil | In-place |
|---|---|---|---|---|
| Bubble Sort | O(n²) | O(1) | Ja | Ja |
| Selection Sort | O(n²) | O(1) | Nein | Ja |
| Insertion Sort | O(n²) | O(1) | Ja | Ja |
| Quick Sort | O(n log n) | O(log n) | Nein | Ja |
| Merge Sort | O(n log n) | O(n) | Ja | Nein |
| Heap Sort | O(n log n) | O(1) | Nein | Ja |
Algorithmus-Design-Prinzipien
Divide and Conquer
- Divide: Problem in kleinere Teilprobleme zerlegen
- Conquer: Teilprobleme rekursiv lösen
- Combine: Lösungen kombinieren
Beispiele: Quick Sort, Merge Sort, Binary Search
Greedy Algorithms
- Lokal optimale Entscheidungen treffen
- Hoffnung auf globale Optimalität
Beispiele: Dijkstra, Kruskal, Huffman Coding
Dynamic Programming
- Optimalstruktur: Überlappende Teilprobleme
- Memoization: Zwischenergebnisse speichern
Beispiele: Fibonacci, Knapsack Problem
Performance-Optimierung
Raum-Zeit-Tradeoff
// Speicherplatz für Geschwindigkeit tauschen
public class FibonacciMemoization {
private static Map<Integer, Long> memo = new HashMap<>();
public static long fibonacci(int n) {
if (n <= 1) return n;
if (memo.containsKey(n)) {
return memo.get(n);
}
long result = fibonacci(n - 1) + fibonacci(n - 2);
memo.put(n, result);
return result;
}
}Early Termination
// Optimierte lineare Suche mit Sentinel
public static int optimizedLinearSearch(int[] array, int target) {
int n = array.length;
// Letztes Element als Sentinel
if (array[n - 1] == target) {
return n - 1;
}
// Letztes Element durch Target ersetzen
int last = array[n - 1];
array[n - 1] = target;
int i = 0;
while (array[i] != target) {
i++;
}
// Original-Wert wiederherstellen
array[n - 1] = last;
return i < n - 1 ? i : -1;
}Vorteile und Nachteile
Vorteile von Algorithmen-Analyse
- Performance-Vorhersage: Abschätzung der Laufzeit
- Algorithmus-Wahl: Richtiges Verfahren auswählen
- Optimierung: Flaschenhälse identifizieren
- Skalierbarkeit: Wachstumsverhalten verstehen
Nachteile
- Theoretische Annahmen: Ignoriert Konstanten
- Praktische Unterschiede: Hardware-Einflüsse
- Komplexität: Mathematische Analyse aufwändig
- Over-Engineering: Vorzeitige Optimierung
Häufige Prüfungsfragen
-
Was ist der Unterschied zwischen Best, Average und Worst Case? Best Case: optimaler Pfad, Average Case: erwartete Performance, Worst Case: schlechtester Pfad.
-
Warum ist Binary Search O(log n) und nicht O(n)? Durch Halbierung des Suchbereichs bei jedem Schritt wird die Suche logarithmisch beschleunigt.
-
Wann verwendet man Insertion Sort statt Quick Sort? Bei kleinen Arrays oder fast sortierten Daten, wo Insertion Sort O(n) erreicht.
-
Was bedeutet In-place bei Sortieralgorithmen? Der Algorithmus sortiert ohne zusätzlichen Speicherplatz (O(1) Platz).