|
Sortieren, Suchen, Greedy, Divide-and-Conquer. Wie man Probleme effizient löst.
Die ersten 4 Topics dieser Kategorie in der Reihenfolge, in der sie aufeinander aufbauen. Wer die durchhat, kann den Rest in beliebiger Reihenfolge angehen.
Wie wächst der Aufwand eines Algorithmus mit der Eingabe-Größe? Konstant, linear, quadratisch, und wann macht der Unterschied wirklich was aus?
Der intuitive Sortieralgorithmus: zwei verschachtelte Schleifen, größere Werte blubbern nach oben. Einfach zu erklären, in der Praxis aber zu langsam: O(n²).
Teile und Herrsche. Garantierte O(n log n) durch rekursives Halbieren plus Merge. Stabil, aber braucht O(n) Zusatzspeicher. Klausur-Klassiker schlechthin.
Der schnellste der Klassiker im Average Case: O(n log n), in-place, partitioniert um einen Pivot. Bei sortiertem Input rutscht er aber auf O(n²) ab.
Wie wächst der Aufwand eines Algorithmus mit der Eingabe-Größe? Konstant, linear, quadratisch, und wann macht der Unterschied wirklich was aus?
Der intuitive Sortieralgorithmus: zwei verschachtelte Schleifen, größere Werte blubbern nach oben. Einfach zu erklären, in der Praxis aber zu langsam: O(n²).
Teile und Herrsche. Garantierte O(n log n) durch rekursives Halbieren plus Merge. Stabil, aber braucht O(n) Zusatzspeicher. Klausur-Klassiker schlechthin.
Der schnellste der Klassiker im Average Case: O(n log n), in-place, partitioniert um einen Pivot. Bei sortiertem Input rutscht er aber auf O(n²) ab.
Bubblesort, Mergesort und Quicksort live nebeneinander. Übersichtstabelle, interaktiver Visualizer und Klausur-Quiz, das die Unterschiede festigt.
Der simpelste Suchalgorithmus: jedes Element prüfen bis Treffer oder Ende. Funktioniert auf jedem Array, sortiert oder nicht. O(n) im Worst Case.
Halbiere den Suchraum bei jedem Schritt. O(log n) statt O(n): bei einer Milliarde Einträgen reichen 30 Vergleiche. Voraussetzung: sortiertes Array.
Lineare und binäre Suche live nebeneinander. Bei welchem n lohnt sich der Aufwand des Sortierens? Wann ist Linear schneller? Klausur-Übersicht.
Zwei fundamentale Datenstrukturen: Stack (LIFO) wie ein Bücherstapel, Queue (FIFO) wie eine Schlange. Alle Operationen O(1). Brücke zu Bäumen und Graphen.
Die wichtigste Datenstruktur überhaupt. Key-Value-Lookup in O(1) durch eine Hash-Funktion. Java HashMap, Python dict. Verstehe Buckets, Kollisionen und Chaining.
Knoten mit Pointern statt zusammenhängendem Speicher. Prepend in O(1), Index-Zugriff in O(n) — die umgekehrte Stärke zum Array. Klausur-Klassiker.
Halbierte Suche durch sortierte Baumstruktur: O(log n) für Suche, Insert, Delete — wenn balanciert. Mit BST-Visualizer und allen vier Traversals (In/Pre/Post/Level-Order). Klausur-Liebling.
Knoten und Kanten — von Maps bis Social Networks. BFS (Queue, ebenenweise) vs. DFS (Stack, in die Tiefe), Adjacency-Repräsentation, kürzester Pfad. Mit Live-Traversal-Animation.