Algorithmen verstehen: Sortieren, Suchen & Graphenalgorithmen
Algorithmen sind das Herz der Informatik. Diese Karteikarten trainieren die wichtigsten Sortier- und Suchalgorithmen, Graphenalgorithmen wie BFS und Dijkstra sowie das Konzept der Zeitkomplexität und der O-Notation. Grundlage für technische Interviews und Prüfungen.
Direkt loslernen
Lade alle 18 Karten mit einem Klick ins Tool. Hast du schon eigene Karten, kannst du die neuen anhängen. Dann lernst du sie mit Wiederholungsplan oder druckst sie als PDF.
Algorithmen durch Visualisierung verstehen
Algorithmen lassen sich am besten an kleinen Beispielen nachverfolgen. Schreibe dir für Sortieralgorithmen 5 bis 8 Zahlen auf und führe den Algorithmus Schritt für Schritt durch. Erst dann machen die Laufzeitklassen wirklich Sinn.
Komplexitätsklassen im Vergleich
- O(1): Konstant, unabhängig von n.
- O(log n): Logarithmisch, binäre Suche, balancierte Bäume.
- O(n): Linear, einfaches Durchlaufen einer Liste.
- O(n log n): Merge Sort, Heap Sort (untere Schranke für vergleichsbasiertes Sortieren).
- O(n²): Bubble Sort, Insertion Sort, nur für kleine Eingaben akzeptabel.
Divide and Conquer als Muster
Merge Sort und Quick Sort zerlegen das Problem rekursiv in kleinere Teilprobleme. Merge Sort ist stabil und garantiert O(n log n). Quick Sort ist in der Praxis meist schneller, hat aber im Worst Case O(n²) (ungünstige Pivotauswahl).
Alle Karten in diesem Set
| Vorderseite | Rückseite |
|---|---|
| O-Notation: was beschreibt sie? | Die asymptotische obere Schranke für die Laufzeit oder den Speicher eines Algorithmus in Abhängigkeit von der Eingabegröße n. |
| Bubble Sort: Zeitkomplexität | O(n²) im Worst und Average Case. O(n) im Best Case (bereits sortiert mit Optimierung). |
| Merge Sort: Zeitkomplexität | O(n log n) in allen Fällen. Stabil. Braucht O(n) zusätzlichen Speicher. |
| Quick Sort: Zeitkomplexität | O(n log n) im Durchschnitt. O(n²) im Worst Case (schlechter Pivot). In-Place möglich. |
| Heap Sort: Zeitkomplexität | O(n log n) garantiert, O(1) zusätzlicher Speicher. Nicht stabil. |
| Binäre Suche: Voraussetzung und Komplexität | Das Array muss sortiert sein. Zeitkomplexität: O(log n). |
| Was ist ein stabiler Sortieralgorithmus? | Er erhält die relative Reihenfolge von Elementen mit gleichem Schlüssel. Merge Sort und Insertion Sort sind stabil, Quick Sort und Heap Sort typischerweise nicht. |
| BFS (Breadth-First Search): Eigenschaften | Durchsucht den Graphen schichtweise. Nutzt eine Queue. Findet kürzesten Pfad (Kantenanzahl) in ungewichteten Graphen. O(V + E). |
| DFS (Depth-First Search): Eigenschaften | Durchsucht den Graphen tiefenorientiert. Nutzt einen Stack (oder Rekursion). Gut für Zyklenerkennung und topologische Sortierung. O(V + E). |
| Dijkstra-Algorithmus: Anwendung | Kürzester Pfad von einem Startknoten zu allen anderen in gewichteten Graphen mit nicht-negativen Kantengewichten. O((V + E) log V) mit Min-Heap. |
| Bellman-Ford: Unterschied zu Dijkstra | Unterstützt negative Kantengewichte. Erkennt negative Zyklen. Langsamer: O(V * E). |
| Dynamische Programmierung: Grundidee | Teile das Problem in überlappende Teilprobleme, löse jedes einmal und speichere das Ergebnis (Memoisation oder Bottom-Up-Tabelle). |
| Greedy-Algorithmus: Charakteristik | Trifft in jedem Schritt die lokal optimale Entscheidung, ohne zurückzublicken. Nicht immer global optimal, aber bei bestimmten Problemen (z.B. Kruskal, Dijkstra) korrekt. |
| Was ist Rekursion? | Eine Funktion ruft sich selbst mit einem kleineren Teilproblem auf. Benötigt einen Basisfall (Abbruchbedingung) und den rekursiven Fall. |
| Master-Theorem: wofür? | Zur Analyse der Laufzeit rekursiver Algorithmen der Form T(n) = a · T(n/b) + f(n). |
| Insertion Sort: Best Case | O(n) bei bereits sortierter Eingabe. Gut für kleine oder fast sortierte Arrays. |
| Was ist Topologische Sortierung? | Lineare Anordnung der Knoten eines DAG (gerichteter azyklischer Graph), sodass für jede Kante (u, v) u vor v kommt. Nur möglich in DAGs. |
| Kruskal-Algorithmus: Anwendung | Findet den minimalen Spannbaum eines Graphen. Sortiert alle Kanten nach Gewicht, fügt sie der Reihe nach hinzu, sofern kein Zyklus entsteht. O(E log E). |
Häufige Fragen
Wann ist Merge Sort besser als Quick Sort?
Merge Sort garantiert O(n log n) in allen Fällen und ist stabil. Quick Sort kann im Worst Case O(n²) erreichen, ist aber in der Praxis oft schneller wegen besserer Cache-Lokalität und geringerem Overhead. Bei verketteten Listen, bei Stabilitätsanforderung und wenn die Laufzeit garantiert sein muss, ist Merge Sort vorzuziehen.
Was ist der Unterschied zwischen BFS und DFS?
BFS erkundet alle Nachbarn eines Knotens, bevor es tiefer geht, nutzt eine Queue. DFS geht so tief wie möglich, bevor es zurückkommt, nutzt einen Stack oder Rekursion. BFS findet kürzeste Pfade (Kantenanzahl) in ungewichteten Graphen, DFS eignet sich besser für Zyklenerkennung und topologische Sortierung (beide laufen in O(V + E)).
Wann verwendet man dynamische Programmierung statt Greedy?
Wenn das Problem überlappende Teilprobleme hat und eine Greedy-Wahl lokal optimal, aber global suboptimal sein könnte. Klassisches Beispiel: Das 0-1-Rucksackproblem lässt sich mit einer einfachen Greedy-Strategie nicht optimal lösen, aber mit DP. Wenn Greedy korrekt ist (z.B. bei Aktivitätsauswahl), ist es schneller.