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 in den Lern-Modus, mische sie, lerne online oder drucke sie als PDF.
Algorithmen durch Visualisierung verstehen
Algorithmen lassen sich am besten an kleinen Beispielen nachverfolgen. Schreibe dir für Sortieralgorithmen 5-8 Zahlen auf und führe den Algorithmus Schritt für Schritt durch. Erst dann macht die Formel 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): Mergesort, Heapsort – optimal für vergleichsbasiertes Sortieren.
- O(n^2): Bubble Sort, Insertion Sort – nur für kleine Eingaben akzeptabel.
Divide and Conquer als Muster
Mergesort und Quicksort teilen das Problem rekursiv in Hälften. Mergesort ist stabil und garantiert O(n log n). Quicksort ist im Durchschnitt schneller, aber O(n^2) im Worst Case (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^2) 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^2) 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 Graph schichtweise. Nutzt Queue. Findet kürzesten Pfad (Kantenanzahl) in ungewichteten Graphen. O(V + E). |
| DFS (Depth-First Search) – Eigenschaften | Durchsucht Graph tiefenorientiert. Nutzt Stack (oder Rekursion). Gut für Zyklen finden, 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 ein, solange kein Zyklus entsteht. O(E log E). |
Häufige Fragen
Warum ist Merge Sort oft 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^2) erreichen, ist aber in der Praxis oft schneller wegen besserer Cache-Lokalität und geringerem Overhead. Für kritische Systeme oder verlinkte Listen 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 ist effizienter für Tiefenoperationen wie Zyklen oder Topologische Sortierung.
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 nicht greedy lösen, aber mit DP. Wenn Greedy korrekt ist (z.B. bei Aktivitätsauswahl), ist es schneller.