Dein Fortschritt:
0 / 0 Aufgaben
1
Übungsaufgaben
Dreißig Ü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 IJedes 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 INennen 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)\)
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.