MINT lernen

Übungen: Laufzeitverhalten abschätzen

Zehn Übungen zur O-Notation — von der Rangfolge der Klassen über das Hochrechnen bis zur Definition mit c und n₀.

Dein Fortschritt:
0 / 0 Aufgaben
1

Übungsaufgaben

Zehn Übungen zum Klicken, Zuordnen, Rechnen und Knobeln — von AFB I bis AFB III. Jede Übung gibt sofort Rückmeldung; wenn Sie nicht weiterkommen, helfen die gestuften Tipps.

A1
Verfahren und Klasse
AFB I

Jedes Verfahren gehört im ungünstigsten Fall zu einer Wachstumsklasse. Ordnen Sie jedem Verfahren seine Klasse zu.

Klicken Sie links einen Eintrag an und dann rechts den passenden — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.
Der Zugriff über den Index kostet unabhängig von \(n\) einen Schritt. Das Maximum braucht genau einen Durchlauf, Insertionsort im ungünstigsten Fall \(\frac{n(n-1)}{2}\) Vergleiche. Jede weitere Sache verdoppelt die Zahl der Teilmengen.
Ansatz: Fragen Sie: Wie ändert sich die Arbeit, wenn \(n\) sich verdoppelt?
Weiter: Konstant, +1 Schritt, doppelt, vierfach, quadriert — das sind die fünf Klassen.
A2
Was liegt in O(n²)?
AFB I

\(O(n^2)\) ist eine obere Schranke. Geben Sie alle Laufzeitfunktionen an, die in \(O(n^2)\) liegen.

Mehrere Antworten sind richtig. Markieren Sie alle zutreffenden und klicken Sie dann auf „Auswahl prüfen“.
Alles, was höchstens quadratisch wächst, liegt in \(O(n^2)\) — auch \(100n\) und \(\log_2 n\), denn ab \(n_0 = 100\) bzw. \(n_0 = 1\) sind sie kleiner als \(n^2\). \(\frac{n^3}{1000}\) überholt \(c \cdot n^2\) für jedes \(c\) irgendwann (ab \(n = 1000c\)).
Ansatz: Prüfen Sie für jede Funktion: Bleibt sie ab einem \(n_0\) unter \(c \cdot n^2\)?
Weiter: Vier Funktionen sind richtig — auch langsam wachsende.
A3
Die Rangfolge
AFB I

Nennen Sie die Wachstumsklassen in aufsteigender Reihenfolge, indem Sie die Karten ordnen — oben die langsamste.

Ziehen Sie die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.
1\(O(1)\) — konstant
2\(O(\log n)\) — logarithmisch
3\(O(n)\) — linear
4\(O(n \log n)\)
5\(O(n^2)\) — quadratisch
6\(O(n^3)\) — kubisch
7\(O(2^n)\) — exponentiell
Jede Klasse liegt in der nächsten: \(O(1) \subset O(\log n) \subset O(n) \subset \ldots \subset O(2^n)\). Die Exponentialfunktion überholt jede Potenz von \(n\).
Ansatz: Setzen Sie \(n = 1024\) ein und vergleichen Sie die Zahlen.
Weiter: \(\log_2 1024 = 10\), \(1024 \cdot 10\), \(1024^2\), … und \(2^{1024}\) ist riesig.
A4
Zehnmal so viele Daten
AFB II

Die Datenmenge wird verzehnfacht. Schätzen Sie ab, wie sich die Zahl der Schritte im ungünstigsten Fall ändert.

Wählen Sie für jede Zeile eine Stufe: 1 = bleibt gleich, 2 = etwa 3,3 Schritte mehr, 3 = mal 10, 4 = mal 100, 5 = mal 1000. Mit der Tastatur: Tab zur Zeile, ←/→ zwischen den Stufen, Enter setzt.
1 = bleibt gleich5 = mal 1000
\(O(1)\)
\(O(\log n)\)
\(O(n)\)
\(O(n^2)\)
\(O(n^3)\)
lineare Suche
Allgemein: \(T(10n) : T(n)\). Für \(n^k\) ist das \(10^k\). Beim Logarithmus kommt \(\log_2 10 \approx 3{,}3\) dazu — die Verzehnfachung ist gut dreimal verdoppeln.
Ansatz: Setzen Sie \(10n\) für \(n\) ein.
Weiter: \((10n)^2 = 100 n^2\) und \(\log_2(10n) = \log_2 n + \log_2 10\).
A5
Hochrechnen
AFB II

Ein Programm sortiert 20 000 Werte mit Insertionsort (ungünstigster Fall, \(O(n^2)\)) in 0,8 s. Berechnen Sie die erwarteten Laufzeiten.

Rechnen Sie die Kette Schritt für Schritt: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.
  1. Insertionsort, 40 000 Werte: s
  2. Insertionsort, 200 000 Werte: s
  3. ein lineares Verfahren, das für 20 000 Werte ebenfalls 0,8 s braucht, bei 200 000 Werten: s
Doppelte Menge: Faktor \(2^2 = 4\), also 3,2 s. Zehnfache Menge: Faktor \(10^2 = 100\), also 80 s. Das lineare Verfahren braucht zehnmal so lange: 8 s — ein Zehntel der quadratischen Zeit.
Ansatz: Bilden Sie zuerst den Faktor \(\frac{n_{\text{neu}}}{n_{\text{alt}}}\).
Weiter: Bei \(O(n^2)\) geht dieser Faktor im Quadrat in die Zeit ein.
A6
Eine Schranke finden
AFB II

Ein Algorithmus braucht \(T(n) = 4n + 7\) Schritte. Zeigen Sie mit der Definition der O-Notation, dass \(T(n) \in O(n)\) gilt, indem Sie die Lücken füllen.

Wählen Sie in jedem Menü den passenden Eintrag und prüfen Sie dann alle auf einmal.
T(n) = 4n + 7
     ≤ 4n + 7 · 
     =  · n      für alle n ≥ 
also T(n) ∈ O()
Für \(n \ge 1\) ist \(7 \le 7n\), also \(4n + 7 \le 11n\). Mit \(c = 11\) und \(n_0 = 1\) ist die Definition erfüllt. Für \(n = 0\) gilt \(7 \le 0\) nicht — deshalb braucht man \(n_0\).
Ansatz: Schätzen Sie die Konstante 7 nach oben durch ein Vielfaches von \(n\) ab.
Weiter: Ab welchem \(n\) gilt \(7 \le 7n\)?
A7
Stimmt's? — Klassen im Kapitel
AFB II Mix

Ordnen Sie die Verfahren des Kapitels in ihre Wachstumsklassen ein und entscheiden Sie bei jeder Aussage, ob sie stimmt.

5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann starten Sie die Serie mit „Neue Runde“ neu.
Aussage 1 von 5

Beim Einordnen immer den Fall nennen: Insertionsort ist im besten Fall linear, im ungünstigsten quadratisch.
Ansatz: Überlegen Sie für jedes Verfahren, ob es auf vorsortierten Daten früher fertig wird.
Weiter: Nur Verfahren mit einer Abbruchmöglichkeit profitieren von günstigen Daten.
A8
P oder Q?
AFB III

Algorithmus P braucht \(50 \cdot n \cdot \log_2 n\) Schritte, Algorithmus Q braucht \(n^2\). Entscheiden Sie Schritt für Schritt, welcher Algorithmus wann vorn liegt.

Spielen Sie den Ablauf Schritt für Schritt durch: Was passiert als Nächstes? Nur die richtige Karte bringt Sie weiter.
    Der große Faktor 50 lässt P bei kleinen Listen verlieren. Für große \(n\) entscheidet die Klasse: \(O(n \log n)\) schlägt \(O(n^2)\).
    Ansatz: Setzen Sie die Zahlen in beide Formeln ein; \(\log_2 16 = 4\), \(\log_2 1024 = 10\).
    Weiter: Gleichstand: \(n^2 = 50\,n \log_2 n\) — teilen Sie durch \(n\).
    A9
    Zehn Dinge mehr
    AFB III Trick

    Ein Programm probiert alle Teilmengen aus und braucht \(T(n) = 2^n\) Schritte. Für \(n = 30\) läuft es eine Sekunde. Bestimmen Sie, wie viele Sekunden es für \(n = 40\) braucht.

    Überlegen Sie selbst und tragen Sie das Ergebnis ein — Enter prüft direkt.
    \(\frac{T(40)}{T(30)} = \frac{2^{40}}{2^{30}} = 2^{10} = 1024\) — also 1024 s, gut 17 Minuten. Wer \(\frac{40}{30} \approx 1{,}3\) rechnet, denkt linear: Bei exponentiellem Wachstum verdoppelt jedes zusätzliche Element die Zeit.
    Ansatz: Bilden Sie den Quotienten \(\frac{2^{40}}{2^{30}}\).
    Weiter: Jedes zusätzliche Element verdoppelt die Zahl der Teilmengen.
    A10
    Aussagen über O
    AFB III

    Beurteilen Sie die Aussagen über die O-Notation.

    Ziehen Sie jede Karte in den passenden Korb — oder wählen Sie sie mit Enter aus und drücken dann die Ziffer des Korbs (0 legt sie zurück).
    1Aussage stimmt
    2Aussage stimmt nicht
    O ist eine obere Schranke: Was in \(O(n)\) liegt, liegt auch in \(O(n^2)\). Konstante Faktoren ändern die Klasse nicht — \(2^{n+1} = 2 \cdot 2^n\). Für kleine \(n\) kann ein quadratisches Verfahren schneller sein.
    Ansatz: Prüfen Sie die Aussagen mit der Definition: Gibt es \(c\) und \(n_0\)?
    Weiter: Ein konstanter Faktor wie 2 oder \(\log_2 10\) steckt in \(c\).