Übung AFB III

Musterlösung: Für \(n = 8\) wäre \(n\log_2 n = 24\). Bei der sortierten Reihung ist beim Mischen jedes linke Element kleiner als jedes rechte; es werden nur die Elemente der linken Hälfte verglichen, der Rest der rechten wird ohne Vergleich angehängt. Ebene 1: \(4\cdot1\), Ebene 2: \(2\cdot2\), Ebene 3: \(1\cdot4\) — zusammen 12 Vergleiche.

Die Behauptung ist widerlegt. Richtig ist: \(n\log_2 n\) ist eine obere Schranke; der ungünstigste Fall liegt bei \(n\log_2 n - n + 1 = 17\), der günstigste bei \(\frac{n}{2}\log_2 n = 12\).

Musterlösung:

static long potenz(long x, int n) {
    if (n == 0) {
        return 1;
    }
    long h = potenz(x, n / 2);
    if (n % 2 == 0) {
        return h * h;
    }
    return h * h * x;
}

Exponenten der Aufrufkette: 1000, 500, 250 (gerade, je 1), 125 (ungerade, 2), 62 (1), 31, 15, 7, 3, 1 (ungerade, je 2), 0 (keine). Summe \(1 + 1 + 1 + 2 + 1 + 2 + 2 + 2 + 2 + 2 = \) 16 Multiplikationen statt 999 — höchstens \(2(\lfloor\log_2 n\rfloor + 1)\).

Musterlösung: \(A(40) = 2\cdot165\,580\,141 - 1 = 331\,160\,281\approx\) 331,2 Mio. Aufrufe. Dieselben Teilprobleme werden immer wieder neu berechnet (z. B. fib(38) zweimal, fib(37) dreimal …), der Aufwand wächst exponentiell. Die Rekursionstiefe ist mit 40 dagegen harmlos.

Die iterative Fassung braucht 40 Schleifendurchläufe. Urteil: Der baumrekursive Ansatz ist für die App ungeeignet — die Rekursion ist hier kein Teile und herrsche, weil sich die Teilprobleme überschneiden.

Musterlösung: Aufrufe: (0, 3) mit mitte = 1 (4 < 8) → (1, 3) mit mitte = 2 (6 < 8) → (2, 3) mit mitte = 2 (6 < 8) → (2, 3) → … Ab links = 2, rechts = 3 bleibt der Bereich gleich, weil mitte = (2 + 3) / 2 = 2 = links. Die Abbruchbedingung wird nie erreicht; es folgt ein StackOverflowError.

Korrektur: mitte + 1 — das Element a[mitte] ist nach dem Vergleich erledigt. Der Fehler tritt immer auf, wenn ein Bereich aus zwei Elementen nach rechts weitergesucht wird.

Musterlösung:

static boolean istPalindrom(String s) {
    if (s.length() <= 1) {
        return true;
    }
    if (s.charAt(0) != s.charAt(s.length() - 1)) {
        return false;
    }
    return istPalindrom(s.substring(1, s.length() - 1));
}

„reliefpfeiler“: Längen 13, 11, 9, 7, 5, 3, 1 — 7 Aufrufe, Ergebnis true. Achtung: istPalindrom("Rentner") liefert false schon im ersten Aufruf, weil 'R' != 'r'; wer Groß- und Kleinschreibung ignorieren will, ruft die Methode mit s.toLowerCase() auf.

Musterlösung: Im sortierten Bereich gilt erstes ≤ mittleres ≤ letztes; der Median ist also das mittlere Element und damit der Median des ganzen Bereichs. Genau die Hälfte der übrigen Werte ist kleiner, die andere größer: 15 = 7 + 1 + 7. Die Teile bleiben sortiert (die Zerlegung tauscht kleinere Werte nur mit sich selbst), also wiederholt sich das: 7 = 3 + 1 + 3, 3 = 1 + 1 + 1.

Offene Aufrufe auf einem Weg: Bereiche der Größe 15, 7, 3, 1 — Rekursionstiefe 4 \(= \log_2 16\), statt 15 mit dem letzten Element als Pivot.

Musterlösung: Mergesort braucht beim letzten Mischen eine Hilfsreihung für alle \(10^6\) Werte: 4 MB — so viel wie die Daten selbst. Der Aufrufstapel ist mit \(\log_2 10^6 + 1\approx21\) Rahmen unbedeutend. Quicksort sortiert in-place; nur der Aufrufstapel wächst, im Mittel auf wenige Dutzend Rahmen. Mit Median-aus-drei ist der ungünstige Fall (Tiefe \(10^6\)) sehr unwahrscheinlich, aber nicht ausgeschlossen.

Bewertung: Bei knappem Speicher ist Quicksort vorzuziehen; wer eine Laufzeitgarantie braucht und die 4 MB übrig hat, nimmt Mergesort.

Musterlösung: Die Bereiche der Basisfälle zerlegen die Reihung lückenlos in einzelne Elemente, also gibt es genau \(n\) Basisfall-Aufrufe. Jeder teilende Aufruf verbindet zwei Teillösungen zu einer; aus \(n\) Teillösungen wird am Ende eine, dafür sind genau \(n - 1\) Zusammenführungen nötig — egal wie ungleich geteilt wird. Summe: \(n + (n - 1) = 2n - 1\).

Für \(n = 1000\): 1999 Aufrufe (davon 999 mit Vergleich). Alternativ per Induktion: \(A(1) = 1\), \(A(n) = 1 + A(p) + A(q)\) mit \(p + q = n\) ergibt \(1 + (2p - 1) + (2q - 1) = 2n - 1\).

Musterlösung: Variante 1: \(k\cdot10^6\). Variante 2: \(10^6\cdot\log_2 10^6 + 20k\approx19\,931\,569 + 20k\). Variante 2 ist günstiger, wenn \(k\cdot(10^6 - 20) > 19\,931\,569\), also \(k > 19{,}93\) — ab 20 Suchen.

Entscheidung: Wird das Archiv regelmäßig durchsucht und selten geändert, lohnt das einmalige Sortieren schon nach wenigen Tagen. Bei ständig neuen Einträgen müsste man die Sortierung erhalten (z. B. durch Einfügen an der richtigen Stelle).

Musterlösung: Die lineare Summe hat Tiefe \(10\,000\) — damit kann der Stapel tatsächlich überlaufen. Die Summe nach Teile und herrsche halbiert: Bereichsgrößen 10 000, 5000, 2500, …, 1 — Tiefe \(\lceil\log_2 10\,000\rceil + 1 = \) 15. Das ist völlig unkritisch.

Stellungnahme: Die These ist zu pauschal. Problematisch ist Rekursion, die das Problem nur um ein Element verkleinert (Tiefe \(n\)) oder überlappende Teilprobleme mehrfach löst (fib). Teile und herrsche hat logarithmische Tiefe und liefert mit Mergesort und Quicksort die schnellsten Sortierverfahren. Rekursion gezielt einsetzen statt immer vermeiden.