MINT lernen

Übungen: Verfahren beurteilen

Zehn Übungen zum Beurteilen rekursiver Verfahren — Laufzeit, Speicher und Tiefe des Aufrufstapels.

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 du nicht weiterkommst, helfen die gestuften Tipps.

A1
Woran man Verfahren misst
AFB I

Gib alle Kriterien an, die zu einer fachlichen Beurteilung eines Sortierverfahrens gehören.

Mehrere Antworten sind richtig. Markiere alle zutreffenden und klicke dann auf „Auswahl prüfen“.
Beurteilt wird das Wachstum des Aufwands mit n — unabhängig vom Rechner. Eine Zeitmessung bei n = 10 sagt darüber nichts, die Länge des Quelltexts auch nicht.
Ansatz: Denke an Zeit, Speicher und eine Eigenschaft des Ergebnisses.
Weiter: Zwei Antworten hängen vom Rechner oder vom Programmierstil ab.
A2
Wie tief wird es?
AFB I

Ordne jedem Aufruf die größte Zahl gleichzeitig offener Aufrufe zu (einschließlich des ersten Aufrufs).

Klicke links einen Eintrag an und dann rechts den passenden — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.
Mergesort halbiert: \(\log_2 4096 + 1 = 13\). Lineare Rekursion (Fakultät, Summe) und Quicksort im ungünstigsten Fall wachsen mit n. Selectionsort arbeitet iterativ — ein einziger Methodenaufruf.
Ansatz: Halbiert die Rekursion den Bereich, oder wird er nur um eins kleiner?
Weiter: \(2^{12} = 4096\).
A3
Stimmt's? — Wachstum
AFB I

Nenne zu jeder Aussage, ob sie stimmt.

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

Faustregel: n² vervierfacht sich, n · log₂ n verdoppelt sich gut, n verdoppelt sich genau.
Ansatz: Setze 2n in die Formeln ein.
Weiter: Denke an eine Eingabe, bei der Insertionsort besonders schnell ist.
A4
Eine Million Datensätze
AFB II

Es sollen \(n = 2^{20} = 1\,048\,576\) Datensätze sortiert werden; ein Rechner schafft \(10^9\) Vergleiche pro Sekunde. Berechne die Werte.

Rechne die Kette Schritt für Schritt: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.
  1. \(\log_2 n =\)
  2. \(n\cdot\log_2 n\) in Millionen (auf 2 Nachkommastellen): Mio.
  3. \(\frac{n(n-1)}{2}\) in Milliarden (auf 2 Nachkommastellen): Mrd.
  4. Rechenzeit von Selectionsort, gerundet: s
Mergesort ist nach etwa 0,02 s fertig, Selectionsort braucht gut 9 Minuten — über 26 000-mal so lange. Der Unterschied wächst mit n immer weiter.
Ansatz: \(2^{20}\) ist die Datenmenge, der Exponent ist der Logarithmus.
Weiter: Zeit = Vergleiche : \(10^9\) pro Sekunde.
A5
Was passiert bei doppelter Datenmenge?
AFB II Mix

Schätze für jede Größe ab, wie sie sich ändert, wenn sich n verdoppelt.

Wähle für jede Zeile eine Stufe: 1 = bleibt gleich, 2 = wächst um 1, 3 = verdoppelt sich, 4 = etwas mehr als doppelt, 5 = vervierfacht sich. Mit der Tastatur: Tab zur Zeile, ←/→ zwischen den Stufen, Enter setzt.
1 = bleibt gleich5 = vervierfacht sich
Vergleiche der binären Suche im ungünstigsten Fall
Vergleiche der linearen Suche im ungünstigsten Fall
Vergleiche von Mergesort
Vergleiche von Selectionsort
Rekursionstiefe von Mergesort
Vergleiche von Quicksort auf sortierten Daten
Logarithmisches Wachstum (binäre Suche, Tiefe von Mergesort) bringt pro Verdopplung nur einen Schritt mehr. Linear verdoppelt, \(n\log_2 n\) etwas mehr, quadratisch vervierfacht.
Ansatz: Ordne jeder Größe zuerst ihre Formel zu: \(\log_2 n\), \(n\), \(n\log_2 n\) oder \(n^2\).
Weiter: Für \(\log_2 n\) gilt: \(\log_2(2n) = \log_2 n + 1\).
A6
Eine Beurteilung prüfen
AFB II

Jonas hat Mergesort und Quicksort in Stichpunkten beurteilt. Überprüfe seine Aussagen und markiere die drei falschen.

In diesem Text stecken Fehler. Klicke genau die falschen Zeilen an — die richtigen musst du stehen lassen.
Typische Verwechslungen: in-place (Quicksort) und stabil (Mergesort) werden oft vertauscht. „Immer“ ist bei Quicksort fast immer falsch — sein Aufwand hängt vom Pivot ab.
Ansatz: Prüfe jede Aussage gegen die Tabelle auf der Inhaltsseite.
Weiter: Achte auf das Wort „immer“.
A7
Speicher für die Hilfsreihung
AFB II

Mergesort sortiert \(10^6\) Werte vom Typ int (je 4 Byte). Bestimme, wie viel Speicher die Hilfsreihung hilf beim letzten Mischen belegt — in MB mit 1 MB = \(10^6\) Byte.

Überlege selbst und trage das Ergebnis ein — Enter prüft direkt.
Das letzte Mischen verbindet beide Hälften: hilf hat \(10^6\) Plätze zu je 4 Byte, also 4 MB — so viel wie die Reihung selbst. Quicksort braucht dafür nichts, nur Platz auf dem Aufrufstapel.
Ansatz: Wie groß ist der Bereich beim letzten Aufruf von mische?
Weiter: Plätze · Byte je Platz.
A8
Sortierte Eingabe, vier Verfahren
AFB III

Vier Verfahren erhalten dieselbe aufsteigend sortierte Reihung mit 1000 Werten. Vergleiche ihre Vergleichszahlen und ordne sie von wenigen zu vielen.

Ziehe die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.
1Insertionsort
2Mergesort
3Quicksort mit Pivot = mittleres Element
4Selectionsort
Gemessen: Insertionsort 999, Mergesort 5 044 (jedes Mischen vergleicht nur die linke Hälfte), Quicksort mit mittlerem Pivot 7 987 (das Pivot ist immer der Median), Selectionsort 499 500. Mit dem letzten Element als Pivot läge Quicksort gleichauf mit Selectionsort.
Ansatz: Welches Verfahren nutzt Vorsortierung aus, welches ignoriert sie komplett?
Weiter: Mergesort braucht bei sortierten Daten etwa \(\frac{n}{2}\log_2 n\), Quicksort mit Median-Pivot etwa \(n\log_2 n\).
A9
Wie viele Aufrufe liegen auf dem Stapel?
AFB III Trick

Mergesort (Code aus 3.3.2) sortiert 1000 Werte und ruft sich dabei insgesamt 1999-mal auf. Untersuche, wie viele Aufrufe von mergesort höchstens gleichzeitig auf dem Aufrufstapel liegen.

Überlege selbst und trage das Ergebnis ein — Enter prüft direkt.
Offen sind immer nur die Aufrufe auf einem Weg von der Wurzel zu einem Blatt: Bereichsgrößen 1000, 500, 250, 125, 63, 32, 16, 8, 4, 2, 1 — also 11 Aufrufe. Die 1999 Aufrufe finden nacheinander statt; jeder beendete Aufruf gibt seinen Platz wieder frei.
Ansatz: Ein Aufruf verschwindet vom Stapel, sobald er beendet ist.
Weiter: Halbiere 1000 so lange (aufrunden), bis 1 erreicht ist, und zähle alle Stufen.
A10
Stellung nehmen
AFB III

Ein Online-Shop behauptet: „Wir sortieren alle Listen mit Quicksort, weil er das schnellste Verfahren ist.“ Nimm Stellung, indem du die Lücken der Stellungnahme füllst.

Wähle in jedem Menü den passenden Eintrag und prüfe dann alle auf einmal.

Quicksort braucht im Mittel etwa Vergleiche und kommt aus. Im ungünstigsten Fall, etwa bei und Pivot = letztes Element, steigt der Aufwand auf , und die Rekursionstiefe wächst bis . Die Aussage stimmt daher nur ; mit einem mittleren oder zufälligen Pivot lässt sich das Risiko verringern.

Eine Stellungnahme wägt ab: Quicksort ist im Mittel sehr schnell und sparsam, hat aber einen quadratischen ungünstigsten Fall mit großer Rekursionstiefe — gerade bei den im Shop häufigen, schon sortierten Listen. Wer eine Garantie braucht, nimmt Mergesort.
Ansatz: Trenne mittleren und ungünstigsten Fall.
Weiter: Welche Listen gibt es in einem Shop oft — und wie verhält sich Quicksort dort?