Kostenlose Multiple-Choice-Übungsfragen zu Algorithmen & Komplexität mit Tipps und Erklärungen, in drei Stufen: Begriffe und Fakten, Konzepte anwenden, Fälle und Analyse.
Welche Komplexitätsklasse wächst für große n am schnellsten?
Gut gemacht. Willst du die nächste?Bereit für die nächste? Jeden Tag 5 neue Aufgaben in jedem Thema.
Ein Algorithmus ist eine endliche Liste präziser Schritte, die ein Problem löst, etwa das Sortieren einer Liste oder das Finden eines Namens in einem Telefonbuch.
Zwei Algorithmen können dasselbe Problem lösen, aber sehr unterschiedlich viel Zeit brauchen. Die Komplexität beschreibt, wie der Aufwand wächst, wenn die Eingabe größer wird.
Die Größe der Eingabe heißt n: die Anzahl der zu sortierenden Elemente, die Länge einer Liste, die Anzahl der Knoten in einem Graphen.
Stell dir vor, du suchst einen Namen in einem Telefonbuch mit 1000 Seiten. Jede Seite zu lesen dauert bis zu 1000 Schritte. Es in der Mitte aufzuschlagen und jedes Mal zu halbieren dauert etwa 10 Schritte.
Die Zeitkomplexität zählt die Schritte. Die Platzkomplexität zählt den zusätzlichen Speicher. Beide werden als Funktion von n geschrieben.
Meist betrachtet man den schlechtesten Fall (Worst Case): den größten Aufwand über alle Eingaben der Größe n. Manchmal ist stattdessen der durchschnittliche oder der beste Fall gefragt.
Antwort: 4 Sekunden. Eine Verdopplung von n multipliziert n² mit 2² = 4, die Zeit steigt also von etwa 1 auf etwa 4 Sekunden. 2 Sekunden wären die Antwort bei linearem Wachstum und 8 bei n³.
Die O-Notation behält nur das, was bei großem n zählt. Du lässt konstante Faktoren weg und behältst nur den am schnellsten wachsenden Term.
Für n = 1000 ist der n²-Term 3 000 000, während 5n nur 5000 ist. Die kleineren Terme verändern die Summe kaum.
Diese Klassen kommen immer wieder vor, vom langsamsten zum schnellsten Wachstum:
Die O-Notation ist eine obere Schranke: Der Aufwand wächst höchstens so schnell. Ω (Omega) ist eine untere Schranke, und Θ (Theta) ist eine scharfe Schranke, sowohl oben als auch unten.
Die Basis eines Logarithmus spielt in der O-Notation keine Rolle, weil sich Logarithmen mit verschiedenen Basen nur um einen konstanten Faktor unterscheiden.
Antwort: O(n²). Für großes n dominiert der n²-Term, und der konstante Faktor 2 entfällt. O(n) behält den falschen Term, und O(2n²) vergisst, die Konstante wegzulassen.
Einige Algorithmen kommen in fast jeder Vorlesung vor. Lerne ihre Komplexitäten als Fakten.
Eine rekursive Funktion ruft sich selbst mit einer kleineren Eingabe auf, bis sie einen Basisfall erreicht, den sie direkt beantwortet. Ihre Laufzeit wird als Rekurrenz geschrieben:
Drei Entwurfsideen sind wissenswert. Teile und herrsche (Divide and Conquer) teilt, löst und kombiniert. Gierige Algorithmen (Greedy) treffen in jedem Schritt die lokal beste Wahl. Dynamische Programmierung speichert die Antworten überlappender Teilprobleme, damit sie nur einmal berechnet werden.
Antwort: O(n²). Bei schlechten Pivotelementen lässt jede Teilung n − 1 Elemente auf einer Seite, was O(n²) ergibt. O(n log n) ist der durchschnittliche Fall von Quicksort und der schlechteste Fall von Merge Sort.
So findest du die Zeitkomplexität eines Codestücks:
Nenne bei einer Theoriefrage zuerst den Algorithmus oder die Idee, die gemeint ist, und rufe dann seine Komplexität und seine Bedingungen ab (sortierte Eingabe, nichtnegative Gewichte, überlappende Teilprobleme).
Folge jedem Schritt. Versuche, den nächsten vorherzusagen, bevor du ihn öffnest.
Was ist die Zeitkomplexität dieses Codes? for i = 1 to n: (j = 1; while j < n: j = j × 2)
n ist die Zahl, bis zu der die Schleifen laufen.
i läuft von 1 bis n in Schritten von 1, die äußere Schleife läuft also n-mal.
j nimmt die Werte 1, 2, 4, 8, … an und hört auf, wenn es n erreicht. Nach k Durchläufen ist j = 2k, die Schleife endet also nach etwa log₂ n Durchläufen.
Die innere Schleife sitzt in der äußeren Schleife, die Anzahlen multiplizieren sich also.
Für n = 1024 läuft die innere Schleife log₂ 1024 = 10-mal, der Rumpf läuft also 1024 · 10 = 10 240-mal. Das ist weit weniger als n² = 1 048 576.
O(n log n)
Antwort: O(n). Nacheinander ausgeführte Schleifen addieren sich: n + n = 2n, die Konstante entfällt, also O(n). O(n²) wäre nur richtig, wenn eine Schleife in der anderen läge.
P enthält Probleme, die in polynomieller Zeit lösbar sind. NP enthält Probleme, deren Lösungen sich in polynomieller Zeit überprüfen lassen. Jedes Problem in P liegt in NP; ob P = NP gilt, ist weiterhin unbekannt.
Lerne Schritt für Schritt in der AppLerne Schritt für Schritt in der App
Welche Notation beschreibt eine obere Schranke für das Wachstum?
O gibt eine obere Schranke an, Ω eine untere Schranke und Θ eine scharfe (asymptotisch exakte) Schranke.
In einem sortierten Array suchst du zwei Elemente mit einer Zielsumme, indem du von jedem Ende einen Zeiger nach innen bewegst. Welche Zeitkomplexität hat das?
Ist die Summe zu klein, rückt der linke Zeiger nach rechts, ist sie zu groß, rückt der rechte Zeiger nach links; es gibt also höchstens n Schritte.
Der Strassen-Algorithmus multipliziert Matrizen mit 7 statt 8 rekursiven Multiplikationen von Blöcken halber Größe. Welche Laufzeit hat er?
Mit a = 7 und b = 2 dominiert nlog₂ 7 den O(n²)-Additionsaufwand, das ergibt etwa n2,81.
Ein Algorithmus ist eine endliche Liste präziser Schritte, die ein Problem löst, etwa das Sortieren einer Liste oder das Finden eines Namens in einem Telefonbuch.
Zwei Algorithmen können dasselbe Problem lösen, aber sehr unterschiedlich viel Zeit brauchen. Die Komplexität beschreibt, wie der Aufwand wächst, wenn die Eingabe größer wird.
Jede Frage hat vier Antwortmöglichkeiten, und nur eine ist richtig. Du hängst fest? Öffne zuerst einen kleinen Tipp und die vollständige Erklärung erst, wenn du sie brauchst.