.svg)
„Algorithmen und Datenstrukturen" — oft schlicht „Algo" — gilt in der Informatik als das Modul, an dem sich entscheidet, wer das Fach verstanden hat. Der Grund: Hier geht es zum ersten Mal nicht darum, ob ein Programm läuft, sondern wie gut es skaliert. Ob eine Suche Millisekunden oder Stunden braucht, hängt selten von der Hardware ab — fast immer von der Wahl der Datenstruktur und des Algorithmus. Genau dieses Denken in Wachstumsklassen prüft die Klausur.
Diese Datenstrukturen-Zusammenfassung führt durch die klausurrelevanten Blöcke in der Reihenfolge, in der sie aufeinander aufbauen: zuerst die Komplexität mit der Big-O-Notation — das Werkzeug, mit dem sich alle folgenden Strukturen bewerten lassen —, dann Arrays und verkettete Listen als Grundbausteine, Stack und Queue, Hashtabellen, binäre Suchbäume und Heaps sowie Graphen im Überblick. Auf der Algorithmen-Seite folgen binäre Suche, die Sortierverfahren von Bubble Sort bis Quicksort, Rekursion mit Teile und herrsche sowie die Strategien Brute Force und Greedy. Jede Struktur wird über die Kosten ihrer Grundoperationen eingeordnet, jedes Verfahren an einem konkreten Beispiel Schritt für Schritt durchgespielt — bewusst in Worten statt in Code, damit der Kern sichtbar bleibt.
Besonderes Gewicht liegt auf den Stellen, an denen in der Algo-Klausur regelmäßig Punkte verloren gehen: Hash-Zugriffe sind nur im Durchschnitt O(1), im Worst Case O(n); das O(1)-Einfügen der verketteten Liste gilt nur bei bereits bekannter Position; die binäre Suche setzt Sortiertheit voraus; und der binäre Suchbaum entartet bei sortiertem Einfügen zur Liste. Die Lernkarten und Übungsfragen auf dieser Seite trainieren genau diese Fälle — vom Bestimmen einer Komplexität aus der Schleifenstruktur über das Zählen der Schritte einer binären Suche bis zum Erkennen eines Sortierverfahrens am Zwischenstand.
Übernimm diese Inhalte kostenfrei in deinen Learnboost Account — dann arbeiten sie für dich weiter: Spaced Repetition bringt jede Karte zurück, kurz bevor du sie vergisst. So stehst du zur nächsten Klausur nicht wieder am Anfang.
Kostenlos starten · Keine Kreditkarte · Deine eigenen Unterlagen bleiben privat
Datenstrukturen organisieren Daten im Speicher, Algorithmen verarbeiten sie — und die Komplexitätsanalyse verbindet beides: Sie sagt voraus, wie der Aufwand wächst, wenn die Eingabe wächst. Wer die Kosten der Grundoperationen kennt, führt fast jede Klausuraufgabe auf eine Frage zurück: Welche Struktur, welches Verfahren passt zur Anforderung?
Die O-Notation ordnet einen Algorithmus einer Wachstumsklasse zu: Sie beschreibt, wie Laufzeit oder Speicherbedarf mit der Eingabegröße n wachsen — nicht, wie viele Millisekunden ein Programm braucht. Konstante Faktoren und untergeordnete Terme entfallen mit gutem Grund: Sie hängen von Maschine und Implementierung ab und ändern das Wachstum nicht. 3n² + 50n + 200 liegt in O(n²), denn für großes n dominiert der quadratische Term — bei n = 1.000 stellt er über 98 Prozent des Gesamtwerts.
Die Klassen im Alltagsvergleich, aufsteigend: O(1) wie der Griff ins nummerierte Regalfach — die Lagergröße ist egal. O(log n) wie das Nachschlagen im Lexikon durch wiederholtes Halbieren: Verdoppelt sich der Umfang, kommt ein einziger Schritt hinzu. O(n) wie das Durchblättern jeder Seite. O(n log n), die Klasse der guten Sortierverfahren. O(n²) wie eine Runde, in der jeder mit jedem anstößt. O(2ⁿ) wie das Durchprobieren aller Teilmengen: Jedes zusätzliche Element verdoppelt die Arbeit. Es gilt die Hierarchie O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ).
Zwei Zählmuster decken die meisten Analyseaufgaben ab: Zwei verschachtelte Schleifen über n Elemente führen auf n·n Durchläufe, also O(n²); wird der Restbereich pro Schritt halbiert, entsteht O(log n) — 1.024 Elemente sind nach 10 Halbierungen auf eines geschrumpft (2¹⁰ = 1.024). Zusätzlich unterscheidet man Best, Average und Worst Case: Die lineare Suche trifft ihr Ziel im besten Fall beim ersten Vergleich, im Mittel nach etwa n/2, im schlimmsten Fall nach n Vergleichen; ohne Zusatz meint eine O-Angabe meist den Worst Case. Neben der Zeit- zählt die Platzkomplexität: Mergesort braucht O(n) Zusatzspeicher, Insertion Sort nur O(1).
Das Array legt Elemente lückenlos hintereinander. Der Indexzugriff kostet O(1), weil sich die Adresse direkt aus Startadresse und Index berechnen lässt; Einfügen oder Löschen in der Mitte kostet O(n), weil alle nachfolgenden Elemente verschoben werden. Das dynamische Array verdoppelt bei Platzmangel seine Kapazität und kopiert um — einzelne Anhänge-Operationen sind dadurch teuer, doch für n Anhänge fallen insgesamt nur rund 2n Kopierschritte an: Anhängen ist amortisiert O(1).
Die verkettete Liste hält je Element einen Knoten mit Verweis auf den Nachfolger, die doppelt verkettete zusätzlich auf den Vorgänger. Einfügen und Löschen kosten O(1) — aber nur bei bereits bekannter Position, etwa über einen Verweis auf den Knoten; die Suche dorthin kostet O(n), Indexzugriff existiert nicht. Der Vergleich ist ein Klausurklassiker: Das Array gewinnt beim Zugriff, die Liste beim Einfügen an bekannter Stelle — die unsortierte Suche kostet in beiden O(n).
Der Stack arbeitet nach LIFO (last in, first out): push legt oben ab, pop entnimmt oben, beides in O(1). Typische Einsätze sind der Aufrufstack, der je Funktionsaufruf einen Rahmen ablegt und ihn beim Rücksprung entfernt, und die Klammerprüfung: öffnende Klammern ablegen, jede schließende muss zur obersten passen. Die Queue arbeitet nach FIFO (first in, first out): hinten einfügen, vorne entnehmen, beides in O(1) — so laufen Warteschlangen wie Druckaufträge und die Breitensuche, die Knoten in Entdeckungsreihenfolge abarbeitet.
Eine Hashtabelle rechnet den Schlüssel per Hashfunktion in einen Index um, etwa Schlüssel modulo Tabellengröße. Treffen zwei Schlüssel denselben Index — bei Größe 10 landen 12 und 22 beide auf Index 2 —, liegt eine Kollision vor. Behandelt wird sie per Verkettung (an jedem Index hängt eine kleine Liste aller Einträge) oder per offener Adressierung (der Eintrag weicht nach einer festen Sondierungsregel auf den nächsten freien Platz aus). Suchen, Einfügen und Löschen kosten im Durchschnitt O(1), im Worst Case — viele Schlüssel auf einem Index — O(n). Der Lastfaktor, Einträge geteilt durch Plätze, steuert das Risiko: Je voller die Tabelle, desto mehr Kollisionen; über einer Schwelle wird vergrößert und neu gehasht.
Ein Baum hat eine Wurzel, innere Knoten und Blätter (Knoten ohne Kinder); die Tiefe eines Knotens ist die Kantenzahl bis zur Wurzel, die Höhe des Baums der längste Pfad von der Wurzel zu einem Blatt, gezählt in Kanten. Im binären Suchbaum (BST) stehen links kleinere, rechts größere Schlüssel. Suchen und Einfügen folgen einem Pfad von der Wurzel abwärts und kosten O(h): ausgeglichen O(log n), entartet O(n). Wie schnell das kippt, zeigt sortiertes Einfügen: 1, 3, 6, 8, 10, 14 erzeugt eine Kette, in der jeder Knoten nur ein rechtes Kind hat — praktisch eine verkettete Liste. Selbstbalancierende Bäume wie der AVL-Baum begrenzen die Höhe durch Rotationen auf O(log n).
Fügt man dagegen 8, 3, 10, 1, 6, 14 ein, entsteht ein ausgeglichener Baum: Wurzel 8, darunter 3 und 10, darunter 1, 6 und 14. Die drei Tiefendurchläufe unterscheiden sich in der Position der Wurzel: Preorder (Wurzel–links–rechts) liefert 8, 3, 1, 6, 10, 14; Inorder (links–Wurzel–rechts) liefert 1, 3, 6, 8, 10, 14; Postorder (links–rechts–Wurzel) liefert 1, 6, 3, 14, 10, 8. Merksatz: Inorder liefert beim BST die sortierte Reihenfolge — bei anderen Binärbäumen gilt das nicht. Der Heap, ein fast vollständiger Binärbaum mit dem kleinsten (Min-Heap) oder größten Element (Max-Heap) an der Spitze, ist die Standardstruktur der Prioritätswarteschlange: Spitzenelement lesen in O(1), Einfügen und Entnehmen in O(log n).
Ein Graph besteht aus Knoten und Kanten — gerichtet oder ungerichtet, gewichtet oder ungewichtet. Als Adjazenzliste speichert er je Knoten die Nachbarliste (Platz proportional zu Knoten plus Kanten, gut für dünn besetzte Graphen), als Adjazenzmatrix eine n·n-Tabelle (Kantenabfrage in O(1), aber O(n²) Platz). Die Breitensuche erkundet mit einer Queue Ebene für Ebene und findet in ungewichteten Graphen kürzeste Wege; die Tiefensuche läuft per Stack oder Rekursion erst in die Tiefe — etwa um Zyklen zu erkennen oder ein Labyrinth vollständig zu durchlaufen.
Die lineare Suche prüft Element für Element: O(n), ohne Voraussetzungen. Die binäre Suche verlangt sortierte Daten und halbiert den Bereich mit jedem Vergleich des mittleren Elements. Beispiel: Gesucht ist 23 in 2, 5, 8, 12, 16, 23, 38, 42, 56, 61, 72, 81, 88, 91, 97. Die Mitte (Position 8) ist 42 — zu groß, weiter links. Neue Mitte (Position 4) ist 12 — zu klein, weiter rechts. Neue Mitte (Position 6) ist 23 — gefunden nach drei Vergleichen. Allgemein genügen rund log₂ n Schritte: 1.024 Elemente sind nach spätestens 10 Halbierungen auf eines eingegrenzt, eine Million nach rund 20.
Die einfachen Verfahren liegen in O(n²). Bubble Sort vertauscht wiederholt benachbarte Elemente in falscher Reihenfolge: Ein Durchlauf über 5, 1, 4, 2 läuft über 1, 5, 4, 2 und 1, 4, 5, 2 zu 1, 4, 2, 5 — das Maximum ist ans Ende gewandert. Insertion Sort fügt jedes Element an die passende Stelle des bereits sortierten Anfangsstücks ein: 7, 3, 5, 2 wird über 3, 7, 5, 2 und 3, 5, 7, 2 zu 2, 3, 5, 7. Selection Sort tauscht wiederholt das Minimum des Restbereichs nach vorn: Aus 4, 2, 7, 1 wird zuerst 1, 2, 7, 4, am Ende 1, 2, 4, 7.
Mergesort arbeitet nach Teile und herrsche: halbieren bis auf Einzelelemente, dann sortierte Hälften reißverschlussartig verschmelzen. log n Ebenen mal O(n) Verschmelzungsarbeit ergeben garantiert O(n log n) — bei O(n) Zusatzspeicher. Quicksort wählt ein Pivot, stellt Kleineres davor und Größeres dahinter und behandelt beide Teile rekursiv: im Mittel O(n log n) und praktisch meist am schnellsten, bei wiederholt ungünstigem Pivot — etwa dem ersten Element auf bereits sortierten Daten — aber O(n²). Stabil heißt ein Verfahren, wenn gleiche Schlüssel ihre Reihenfolge behalten: Wer eine alphabetische Liste stabil nach Note sortiert, behält innerhalb jeder Note die alphabetische Ordnung. Bubble, Insertion und Mergesort sind stabil, Selection Sort und Quicksort in der üblichen Form nicht. Faustregel: Insertion Sort für kleine oder fast sortierte Eingaben, Mergesort für Garantie und Stabilität, Quicksort als schneller Allrounder.
Teile-und-herrsche-Verfahren führen ein Problem auf kleinere Instanzen desselben Problems zurück und kombinieren die Teillösungen. Der Rekursionsbaum macht die Kosten zählbar: Jede Ebene versammelt die Teilprobleme einer Halbierungsstufe; bei Mergesort fällt pro Ebene O(n) Arbeit an, nach log n Ebenen ist die Elementgröße erreicht — zusammen O(n log n). Jeder offene Aufruf belegt zudem einen Rahmen auf dem Aufrufstack: Die Rekursionstiefe bestimmt den Platzbedarf, und ohne erreichbare Abbruchbedingung läuft der Stack über.
Brute Force probiert systematisch alle Möglichkeiten — korrekt, aber oft exponentiell teuer, etwa beim Test aller Teilmengen. Greedy trifft in jedem Schritt die lokal beste Wahl und schaut nie zurück: Beim Wechselgeld mit Euro-Münzen führt „immer die größte passende Münze" zur minimalen Münzzahl. Greedy ist schnell, aber nicht automatisch korrekt — mit den Münzwerten 1, 3 und 4 liefert es für den Betrag 6 die Zerlegung 4 + 1 + 1, optimal wäre 3 + 3. Daraus folgt die Grundregel des algorithmischen Problemlösens: erst Korrektheit, dann Effizienz — ein schnelles Verfahren mit falschen Ergebnissen löst das Problem nicht.
Arbeite mit dieser Zusammenfassung weiter — kostenfrei in deinem Learnboost Account.
Zusammenfassung übernehmenFrage antippen, um die Antwort aufzudecken.
Die Wachstumsklasse eines Algorithmus: wie Laufzeit oder Speicherbedarf mit der Eingabegröße n wachsen. Konstante Faktoren und untergeordnete Terme bleiben außen vor — es zählt das Verhalten für großes n, nicht die exakte Zeit auf einer bestimmten Maschine.
Für großes n dominiert der am schnellsten wachsende Term: Bei n = 1.000 stellt 3n² über 98 Prozent des Gesamtwerts. Konstante Faktoren hängen von Maschine und Implementierung ab und ändern die Wachstumsklasse nicht. 3n² + 50n + 200 liegt deshalb in O(n²).
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ). O(1): Griff ins nummerierte Regalfach. O(log n): Nachschlagen im Lexikon durch Halbieren. O(n): jede Seite durchblättern. O(n log n): gute Sortierverfahren. O(n²): jeder stößt mit jedem an. O(2ⁿ): alle Teilmengen durchprobieren — jedes weitere Element verdoppelt die Arbeit.
Best Case: günstigste Eingabe — das Ziel steht vorn, ein Vergleich. Average Case: erwarteter Aufwand — im Mittel etwa n/2 Vergleiche. Worst Case: ungünstigste Eingabe — das Ziel steht hinten oder fehlt, n Vergleiche. Ohne Zusatz meint eine O-Angabe meist den Worst Case.
Zeitkomplexität zählt Rechenschritte, Platzkomplexität den zusätzlich belegten Speicher — beide als Funktion von n. Beispiel: Mergesort läuft in O(n log n) Zeit, braucht aber O(n) Zusatzspeicher für das Verschmelzen; Insertion Sort läuft in O(n²), kommt aber mit O(1) Zusatzspeicher aus.
Die Elemente liegen lückenlos hintereinander: Die Adresse ergibt sich direkt aus Startadresse plus Index mal Elementgröße — Zugriff in konstanter Zeit. Beim Einfügen oder Löschen in der Mitte müssen dagegen alle nachfolgenden Elemente um eine Position verschoben werden, im Mittel die Hälfte — O(n).
Bei vollem Speicher verdoppelt das Array seine Kapazität und kopiert alle Elemente um. Diese teuren Momente sind selten: Für n Anhänge fallen insgesamt nur rund 2n Kopierschritte an (1 + 2 + 4 + … Umkopien). Über alle Operationen gemittelt bleibt das Anhängen konstant.
Array: Indexzugriff O(1), Einfügen und Löschen in der Mitte O(n) wegen Verschieben. Liste: Einfügen und Löschen O(1) — aber nur bei bereits bekannter Position; die Suche dorthin kostet O(n), einen Indexzugriff gibt es nicht. Die doppelt verkettete Liste verweist zusätzlich auf den Vorgänger und löscht bekannte Knoten ohne Vorgängersuche. Unsortierte Suche: in beiden O(n).
LIFO — last in, first out: push legt oben ab, pop entnimmt oben, beides O(1). Typische Einsätze: der Aufrufstack, der je Funktionsaufruf einen Rahmen ablegt und ihn beim Rücksprung entfernt, und die Klammerprüfung — öffnende Klammern ablegen, jede schließende muss zur obersten passen; am Ende muss der Stack leer sein.
FIFO — first in, first out: enqueue fügt hinten an, dequeue entnimmt vorne, beides O(1). Typische Einsätze: Warteschlangen wie Druckaufträge, die in Eingangsreihenfolge abgearbeitet werden, und die Breitensuche, die Knoten in der Reihenfolge ihrer Entdeckung bearbeitet.
Eine Hashfunktion rechnet den Schlüssel in einen Index um, etwa Schlüssel modulo Tabellengröße. Kollision: Zwei Schlüssel treffen denselben Index — bei Tabellengröße 10 landen 12 und 22 beide auf Index 2. Zugriffe kosten im Durchschnitt O(1), im Worst Case — viele Schlüssel auf einem Index — O(n).
Verkettung: An jedem Index hängt eine kleine Liste aller dort gelandeten Einträge — Kollisionen verlängern nur die Liste. Offene Adressierung: Der Eintrag weicht nach einer festen Sondierungsregel auf den nächsten freien Platz der Tabelle aus — das braucht freie Plätze und reagiert empfindlich auf einen hohen Lastfaktor (Einträge geteilt durch Plätze).
O(h): Beide folgen einem Pfad von der Wurzel abwärts, h ist die Höhe des Baums. Ausgeglichen gilt h ≈ log₂ n, also O(log n). Entartet der Baum — sortiertes Einfügen von 1, 3, 6, 8, 10, 14 erzeugt eine Kette —, wird h = n − 1 und die Suche O(n). Selbstbalancierende Bäume wie der AVL-Baum halten die Höhe per Rotationen bei O(log n).
In der Position der Wurzel: Preorder Wurzel–links–rechts, Inorder links–Wurzel–rechts, Postorder links–rechts–Wurzel. Beim binären Suchbaum liefert der Inorder-Durchlauf die aufsteigend sortierte Reihenfolge — bei beliebigen Binärbäumen gilt das nicht.
Voraussetzung: sortierte Daten. Sie vergleicht das mittlere Element mit dem Ziel und macht links oder rechts weiter — pro Vergleich halbiert sich der Bereich. 1.024 Elemente sind nach spätestens 10 Halbierungen auf eines eingegrenzt (2¹⁰ = 1.024); die lineare Suche bräuchte im schlimmsten Fall 1.024 Vergleiche.
Teile: das Array halbieren, bis Einzelelemente übrig sind. Herrsche: je zwei sortierte Teile reißverschlussartig zu einem sortierten Ganzen verschmelzen. Es gibt log n Halbierungsebenen, und jede Ebene kostet O(n) Verschmelzungsarbeit — zusammen O(n log n), garantiert auch im Worst Case, bei O(n) Zusatzspeicher.
Ein fast vollständiger Binärbaum, in dem jeder Knoten kleiner (Min-Heap) beziehungsweise größer (Max-Heap) als seine Kinder ist. Das Spitzenelement steht in O(1) bereit, Einfügen und Entnehmen kosten O(log n) durch Aufsteigen beziehungsweise Absinken. Standardstruktur der Prioritätswarteschlange: Entnommen wird nach Priorität, nicht nach Eingangsreihenfolge.
Der Rekursionsbaum ordnet jeder Ebene die Teilprobleme einer Halbierungsstufe zu; die Arbeit wird ebenenweise summiert — bei Mergesort O(n) pro Ebene mal log n Ebenen, zusammen O(n log n). Jeder offene Aufruf belegt einen Rahmen auf dem Aufrufstack: Die Rekursionstiefe bestimmt den Platzbedarf, und ohne erreichbare Abbruchbedingung läuft der Stack über.
Brute Force probiert systematisch alle Möglichkeiten — korrekt, aber oft exponentiell teuer. Greedy wählt in jedem Schritt die lokal beste Option und schaut nie zurück — schnell, aber nicht automatisch korrekt: Mit den Münzwerten 1, 3 und 4 zerlegt Greedy den Betrag 6 in 4 + 1 + 1, optimal wäre 3 + 3. Grundregel: erst Korrektheit, dann Effizienz.
Lerne diese Karten mit Spaced Repetition weiter — kostenfrei in deinem Learnboost Account.
Lernkarten übernehmenLösung:
Das Verfahren liegt in O(n²): Für jedes der n Elemente laufen n − 1 Vergleiche, insgesamt n·(n − 1). Der lineare Anteil und konstante Faktoren entfallen — übrig bleibt die quadratische Klasse.
Verschachtelte Schleifen über dieselbe Eingabe sind das Standardmuster für O(n²): n·(n − 1) ≈ n² Vergleiche, bei n = 1.000 also rund eine Million. Zum Vergleich: Mit einer Hashtabelle ließe sich dieselbe Duplikatsuche im Durchschnitt in O(n) lösen — jedes Element einmal nachschlagen und eintragen. Genau dieser Kontrast zwischen naiver Doppelschleife und passender Datenstruktur ist ein Klausurklassiker.
Lösung:
Drei Vergleiche: Zuerst wird die Mitte 42 geprüft — 23 ist kleiner, weiter links. Dann die Mitte 12 der linken Hälfte — 23 ist größer, weiter rechts. Dann die 23 selbst — gefunden.
Schritt 1: Die Mitte des Bereichs Position 1–15 ist Position 8 mit dem Wert 42; wegen 23 < 42 geht es im Bereich 1–7 weiter. Schritt 2: Dessen Mitte ist Position 4 mit dem Wert 12; wegen 23 > 12 geht es im Bereich 5–7 weiter. Schritt 3: Dessen Mitte ist Position 6 mit dem Wert 23 — Treffer nach drei Vergleichen. Mehr als vier Vergleiche kann es bei 15 Elementen nie geben, denn der Bereich schrumpft über 15, 7, 3, 1.
Lösung:
Eine Queue: Sie arbeitet nach dem FIFO-Prinzip — enqueue hängt hinten an, dequeue entnimmt vorne, beides in konstanter Zeit.
„Eingangsreihenfolge erhalten, hinten einfügen, vorne entnehmen" ist die Definition der Queue (first in, first out). Ein Stack würde stets den neuesten Auftrag zuerst liefern. Ein sortiertes Array ordnet nach Wert statt nach Eingang und kostet beim Einfügen O(n). Ein binärer Suchbaum beantwortet Ordnungsfragen, keine Reihenfolgefragen — und liegt bei O(h) je Operation.
Lösung:
Insertion Sort: Der vordere Teil ist nach jedem Schritt in sich sortiert und wächst um ein Element, der hintere Teil bleibt unverändert in der Ausgangsreihenfolge stehen — genau das zeigen beide Zwischenstände.
Insertion Sort fügt das jeweils nächste Element an der richtigen Stelle des sortierten Anfangsstücks ein: Nach dem Einfügen der 1 steht vorn 1, 4, 7, nach dem Einfügen der 6 steht vorn 1, 4, 6, 7 — die 3 wartet unverändert am Ende. Selection Sort hätte nach zwei Schritten die beiden kleinsten Werte an den endgültigen Positionen (1, 3, …). Bubble Sort hätte nach dem ersten Durchlauf das Maximum 7 ans Ende befördert (4, 1, 6, 3, 7). Mergesort arbeitet über getrennt sortierte Hälften, die verschmolzen werden — solche Zwischenstände entstehen dort nicht.
Lösung:
Optimal ist die binäre Suche: Tippe stets die Mitte des verbleibenden Bereichs. Nach jeder Antwort ist der Bereich höchstens halb so groß — von 1.000.000 auf 500.000, dann 250.000 und so weiter. Da 2²⁰ = 1.048.576 die Million übersteigt, ist der Bereich nach spätestens 20 Halbierungen auf eine einzige Zahl eingegrenzt; rund 20 Tipps genügen. Das ist O(log n). Naives Durchprobieren (1, 2, 3, …) ist lineare Suche in O(n): im schlimmsten Fall 1.000.000 Tipps, im Mittel etwa 500.000. Der Vergleich zeigt den Kern der logarithmischen Klasse: Eine Verdopplung des Zahlenraums kostet nur einen einzigen zusätzlichen Tipp.
Bewertet werden drei Bestandteile: die Strategie (immer die Mitte — jeder andere Tipp lässt im ungünstigen Fall mehr als die Hälfte übrig), die Abschätzung (1.024 = 2¹⁰, eine Million ≈ 2²⁰, also rund 20 Schritte) und die Einordnung O(log n) gegenüber O(n). Wichtig ist die Voraussetzung: Die Strategie funktioniert nur, weil die Antworten „größer/kleiner" den Zahlenraum ordnen — dieselbe Rolle spielt bei der binären Suche die Sortiertheit der Daten.
Lösung:
Sinnvoll sind die Hashtabelle für den Schlüssel-Lookup, der binäre Suchbaum für die sortierte Ausgabe und der Heap für die Entnahme nach Priorität.
Die Hashtabelle liefert Lookups im Durchschnitt in O(1), hält aber keine Ordnung. Der binäre Suchbaum liefert per Inorder-Durchlauf jederzeit die sortierte Reihenfolge. Der Heap hält das Spitzenelement in O(1) bereit und entnimmt es in O(log n). Für die Eingangsreihenfolge wäre eine Queue richtig — der Stack kehrt sie um. Positionszugriff ist die Stärke des Arrays mit O(1); die verkettete Liste muss dafür in O(n) durchlaufen werden.
Lösung:
Zutreffend sind die Durchschnitts- und Worst-Case-Angabe der Hashtabelle, die höhenabhängigen Kosten des binären Suchbaums und das amortisiert konstante Anhängen beim dynamischen Array.
Hash-Zugriffe sind nur im Durchschnitt konstant — fallen viele Schlüssel auf denselben Index, degeneriert der Zugriff zu O(n). Beim binären Suchbaum bestimmt die Höhe die Kosten: ausgeglichen O(log n), zur Kette entartet O(n). Die binäre Suche setzt Sortiertheit zwingend voraus — auf unsortierten Daten sind ihre Halbierungsentscheidungen wertlos. Einfügen in der Arraymitte verschiebt alle nachfolgenden Elemente und kostet O(n). Beim dynamischen Array verteilen sich die seltenen Kopierkosten der Verdopplung auf viele Anhänge-Operationen.
Lösung:
Zutreffend sind die sortierte Inorder-Reihenfolge, die Position der Wurzel 20 am Anfang des Preorder- und am Ende des Postorder-Durchlaufs sowie die Einordnung der 12 als linkes Kind der 15.
Es entsteht ein ausgeglichener Baum: 20 als Wurzel, darunter 10 und 30, darunter 5, 15, 25, 35. Inorder (links–Wurzel–rechts) liefert beim binären Suchbaum immer die sortierte Reihenfolge; Preorder besucht die Wurzel zuerst, Postorder zuletzt. Die Suchwege zu 25 und zu 5 sind gleich lang — jeweils drei Vergleiche (20, 30, 25 beziehungsweise 20, 10, 5). Die 12 läuft den Pfad 20 → 10 → 15 und wird dort linkes Kind, denn 12 ist kleiner als 15. Sortiertes Einfügen ergäbe dagegen eine entartete Kette: Die Gestalt eines binären Suchbaums hängt von der Einfügereihenfolge ab.
Lösung:
Schritt 1: Bereich Position 1–15, Mitte ist Position 8 mit dem Wert 42; 61 ist größer — weiter rechts im Bereich 9–15. Schritt 2: Mitte ist Position 12 mit dem Wert 81; 61 ist kleiner — weiter links im Bereich 9–11. Schritt 3: Mitte ist Position 10 mit dem Wert 61 — Treffer. Insgesamt drei Vergleiche. Sortiertheit ist Voraussetzung, weil jede Links-rechts-Entscheidung eine Hälfte ungesehen verwirft: Nur wenn links der Mitte ausschließlich kleinere und rechts ausschließlich größere Werte stehen, kann der Zielwert in der verworfenen Hälfte sicher nicht liegen. Auf unsortierten Daten dürfte nach dem Vergleich mit 42 die linke Hälfte nicht verworfen werden — die 61 könnte dort stehen.
Volle Punktzahl verlangt den protokollierten Ablauf (Bereich, Mitte, Entscheidung je Schritt), die korrekte Vergleichszahl drei und die Begründung der Voraussetzung. Kern der Begründung: Die binäre Suche verwirft in jedem Schritt die Hälfte der Daten, ohne sie anzusehen — zulässig ist das nur, wenn die Sortierung garantiert, dass der gesuchte Wert dort nicht stehen kann. Zur Einordnung: Bei 15 Elementen sind höchstens vier Vergleiche nötig, denn der Bereich schrumpft über 15, 7, 3, 1 — das ist die O(log n)-Signatur des Verfahrens.
Lösung:
50 wird Wurzel. 30 ist kleiner — linkes Kind; 70 ist größer — rechtes Kind. 20 läuft über 50 und 30 nach links, 40 über 50 und 30 nach rechts; 60 läuft über 50 und 70 nach links, 80 über 50 und 70 nach rechts. Ergebnis: Wurzel 50, zweite Ebene 30 und 70, dritte Ebene 20, 40, 60, 80 — ein vollständig ausgeglichener Baum der Höhe 2. Eine Suche braucht höchstens drei Vergleiche, allgemein O(log n). Beim aufsteigenden Einfügen 20, 30, 40, 50, 60, 70, 80 wird jeder neue Wert als größter bisheriger zum rechten Kind des zuletzt eingefügten Knotens: Es entsteht eine Kette der Höhe 6, der Baum ist zur Liste entartet, die Suche kostet bis zu sieben Vergleiche — allgemein O(n). Die Suchkosten hängen also nicht von der Wertemenge ab, sondern über die Höhe von der Einfügereihenfolge.
Bewertet werden der korrekt aufgebaute Baum (50 als Wurzel, darunter 30 und 70, darunter 20, 40, 60, 80), die Höhe 2, die entartete Kette der Höhe 6 beim sortierten Einfügen und der Kostenvergleich O(log n) gegenüber O(n). Der Kontrast ist der Kern der Aufgabe: Dieselben sieben Werte erzeugen je nach Reihenfolge den besten und den schlechtesten Fall — deshalb geben Lehrbücher die Kosten des binären Suchbaums ehrlich als O(h) an. Selbstbalancierende Varianten wie der AVL-Baum begrenzen h durch Rotationen auf O(log n), unabhängig von der Einfügereihenfolge.
Übe diese Probeklausur interaktiv — kostenfrei in deinem Learnboost Account.
Probeklausur übernehmenAlles auf dieser Seite kannst du kostenfrei in deinen Learnboost Account übernehmen — und dort deutlich mehr daraus machen:
Bessere Noten beginnen bei Learnboost.
Erstellt von Learnboost-Redaktion. KI-gestützt erstelltes Originalwerk, redaktionell geprüft.
Inhalte melden: content@learnboost.tech
