Die Messreihe
14 BEAFB I–IIIm Informatikkurs wurden drei Sortierverfahren mit einem Zähler für Vergleiche ausgestattet. Verfahren A erhielt zufällige Daten, Verfahren B ebenfalls zufällige Daten, Verfahren C bereits aufsteigend sortierte Daten. Die Namen der Verfahren wurden in der Tabelle weggelassen; es handelt sich um Selectionsort, Insertionsort und Mergesort.
| n | Verfahren A | Verfahren B | Verfahren C |
|---|---|---|---|
| 1 000 | 499 500 | 8 732 | 999 |
| 2 000 | 1 999 000 | 19 443 | 1 999 |
| 4 000 | 7 998 000 | 42 850 | 3 999 |
- Ermitteln Sie für jedes Verfahren, um welchen Faktor die Zahl der Vergleiche bei Verdopplung von \(n\) wächst. (3 BE)
- Ordnen Sie den Verfahren A, B und C die Namen Selectionsort, Insertionsort und Mergesort zu und begründen Sie jede Zuordnung. (4 BE)
- Schätzen Sie für alle drei Verfahren die Zahl der Vergleiche bei \(n = 1\,000\,000\) ab und geben Sie die Rechenzeit bei \(10^9\) Vergleichen pro Sekunde an. (4 BE)
- Nennen Sie zwei weitere Kriterien außer der Zahl der Vergleiche, nach denen die Verfahren beurteilt werden sollten, und ordnen Sie Mergesort danach ein. (3 BE)
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
A: \(1\,999\,000 : 499\,500 \approx 4{,}00\) und \(7\,998\,000 : 1\,999\,000 \approx 4{,}00\). B: \(19\,443 : 8\,732 \approx 2{,}23\) und \(42\,850 : 19\,443 \approx 2{,}20\). C: \(1\,999 : 999 \approx 2{,}00\) und \(3\,999 : 1\,999 \approx 2{,}00\).
Erwartungshorizont zu Aufgabe b)
A = Selectionsort: Faktor 4 bedeutet quadratisches Wachstum; die Werte sind exakt \(\frac{n(n-1)}{2}\), unabhängig von den Daten. B = Mergesort: Faktor etwas über 2 passt zu \(n\log_2 n\); die Werte liegen knapp unter \(n\log_2 n\) (z. B. \(1000\cdot\log_2 1000\approx9966\)). C = Insertionsort: genau \(n - 1\) Vergleiche — der beste Fall bei sortierter Eingabe, lineares Wachstum.
Erwartungshorizont zu Aufgabe c)
Selectionsort: \(\frac{10^6\cdot(10^6-1)}{2}\approx5\cdot10^{11}\) Vergleiche, rund 500 s. Mergesort: \(10^6\cdot\log_2 10^6\approx2\cdot10^7\) (die Messwerte liegen etwas darunter, etwa \(1{,}9\cdot10^7\)), rund 0,02 s. Insertionsort bei sortierter Eingabe: \(10^6 - 1\approx10^6\), rund 0,001 s.
Erwartungshorizont zu Aufgabe d)
Zum Beispiel Zusatzspeicher (Mergesort braucht eine Hilfsreihung der Länge \(n\)), Rekursionstiefe (Mergesort nur etwa \(\log_2 n + 1\)), Stabilität (Mergesort ist stabil) oder das Verhalten im ungünstigsten Fall (Mergesort garantiert \(n\log_2 n\)). Zwei Kriterien mit Einordnung genügen.
Zwei Wege zur Summe
16 BEAFB II–IIIZwei Schüler haben die Summe aller Elemente einer Reihung rekursiv berechnet: summeLinear(a, 0) verkleinert das Problem um ein Element, summeTH(a, 0, a.length - 1) halbiert es. Beide liefern für {5, 3, 8, 1, 9, 2, 7, 4} das Ergebnis 39. Für eine Reihung mit 100 000 Elementen bricht einer der Aufrufe mit StackOverflowError ab.
static int summeLinear(int[] a, int i) {
if (i == a.length - 1) {
return a[i];
}
return a[i] + summeLinear(a, i + 1);
}
static int summeTH(int[] a, int links, int rechts) {
if (links == rechts) {
return a[links];
}
int mitte = (links + rechts) / 2;
return summeTH(a, links, mitte) + summeTH(a, mitte + 1, rechts);
}- Vergleichen Sie beide Methoden für eine Reihung mit 8 Elementen hinsichtlich der Anzahl der Aufrufe, der Anzahl der Additionen und der Rekursionstiefe. (4 BE)
- Erklären Sie, welche der beiden Methoden bei 100 000 Elementen abbricht und warum die andere nicht abbricht. (4 BE)
- Leiten Sie für
summeTHdie Rekursionstiefe für \(n = 2^k\) Elemente her und geben Sie sie für \(n = 100\,000\) an. (4 BE) - Nehmen Sie Stellung zu der Aussage: „Rekursion ist immer schlechter als eine Schleife.“ (4 BE)
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
| summeLinear | summeTH | |
|---|---|---|
| Aufrufe | 8 | 15 (8 Basisfälle + 7 teilende) |
| Additionen | 7 | 7 |
| Rekursionstiefe | 8 | 4 |
Beide rechnen gleich viel (7 Additionen). summeTH braucht fast doppelt so viele Aufrufe, hat aber eine viel kleinere Tiefe.
Erwartungshorizont zu Aufgabe b)
summeLinear bricht ab: Der Aufruf für Index i kann erst enden, wenn summeLinear(a, i + 1) fertig ist — alle 100 000 Aufrufe sind gleichzeitig offen und belegen je einen Eintrag auf dem begrenzten Aufrufstapel. summeTH hat nur etwa 18 gleichzeitig offene Aufrufe; die übrigen der rund 200 000 Aufrufe sind zu diesem Zeitpunkt schon beendet oder noch nicht begonnen.
Erwartungshorizont zu Aufgabe c)
Auf Ebene \(d\) haben die Bereiche \(\frac{n}{2^d}\) Elemente. Der Basisfall ist erreicht, wenn \(\frac{n}{2^d} = 1\), also \(d = \log_2 n = k\). Mit dem ersten Aufruf (Ebene 0) sind höchstens \(k + 1 = \log_2 n + 1\) Aufrufe gleichzeitig offen. Für \(n = 100\,000\): \(\lceil\log_2 100\,000\rceil + 1 = 17 + 1 = 18\).
Erwartungshorizont zu Aufgabe d)
Die Aussage ist zu pauschal. Dafür: Jeder Aufruf kostet Zeit und Stapelspeicher; lineare Rekursion wie summeLinear hat Tiefe \(n\) und kann abstürzen, eine Schleife braucht nur konstanten Speicher. Rekursion mit überlappenden Teilproblemen kann sogar Arbeit vervielfachen. Dagegen: Nach Teile und herrsche entstehen Verfahren wie Mergesort und Quicksort mit \(n\log_2 n\) statt \(n^2\) Vergleichen und nur logarithmischer Tiefe; rekursive Lösungen sind außerdem oft kürzer und leichter zu verstehen (z. B. Traversierung von Bäumen). Fazit: Rekursion ist dann schlechter, wenn sie das Problem nur um ein Element verkleinert; halbiert sie es, ist sie gleichwertig oder überlegen.