MINT lernen

Abituraufgaben: Effizienz beurteilen

Zwei Aufgaben im Abiturformat — vom Online-Shop mit täglichen Preisabfragen bis zur Liste der besten zehn.

Dein Fortschritt:
0 / 0 Aufgaben
1

Preisabfragen im Online-Shop

12 BEAFB II

Ein Online-Shop verwaltet 50 000 Artikel in einer Reihung, zunächst unsortiert nach Artikelnummer. Täglich gibt es etwa 100 000 Preisabfragen über die Artikelnummer. Nachts werden bis zu 200 neue Artikel am Ende angehängt. Gerechnet wird jeweils im ungünstigsten Fall.

  1. Vergleichen Sie für einen Tag den Aufwand zweier Strategien: (1) jede Abfrage mit linearer Suche; (2) nachts mit Selectionsort sortieren und tagsüber binär suchen. (4 BE)
  2. Begründen Sie, warum ab der zweiten Nacht Insertionsort statt Selectionsort die bessere Wahl ist, und schätzen Sie seinen Aufwand ab. (3 BE)
  3. Erläutern Sie den Speicherbedarf der Strategien und ob die Stabilität des Sortierverfahrens hier eine Rolle spielt. (2 BE)
  4. Nehmen Sie abschließend Stellung, welche Kombination von Verfahren Sie dem Shop empfehlen. (3 BE)

Hinweise

Hinweis zu Aufgabe a)
Selectionsort: \(\frac{n(n-1)}{2}\) Vergleiche; binäre Suche: \(\lfloor\log_2 n\rfloor + 1\).
Hinweis zu Aufgabe b)
Wie sieht die Reihung aus, wenn nur 200 neue Artikel hinten angehängt wurden?
Hinweis zu Aufgabe c)
Legen die Verfahren eine zweite Reihung an? Kann es gleiche Artikelnummern geben?
Hinweis zu Aufgabe d)
Ein Fazit mit Begründung und Bedingung.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

(1) \(100\,000 \cdot 50\,000 = 5 \cdot 10^9\) Vergleiche. (2) Sortieren \(\frac{50\,000 \cdot 49\,999}{2} = 1\,249\,975\,000\), dazu \(100\,000 \cdot 16 = 1\,600\,000\) für die binären Suchen (\(\lfloor\log_2 50\,000\rfloor + 1 = 16\)) — zusammen etwa \(1{,}25 \cdot 10^9\). Strategie (2) braucht nur rund ein Viertel; fast ihr ganzer Aufwand steckt im Sortieren.

Erwartungshorizont zu Aufgabe b)

Die ersten 50 000 Artikel sind bereits sortiert; Insertionsort braucht für sie je nur einen Vergleich (49 999). Jeder der 200 neuen Artikel wandert höchstens durch den ganzen sortierten Teil: höchstens etwa \(200 \cdot 50\,200 \approx 10^7\) Vergleiche. Selectionsort nutzt die Vorsortierung nicht und bräuchte wieder \(1{,}25 \cdot 10^9\) — rund hundertmal mehr.

Erwartungshorizont zu Aufgabe c)

Lineare und binäre Suche sowie Selection- und Insertionsort arbeiten in-place: Zusatzspeicher \(O(1)\). Stabilität ist unerheblich, weil Artikelnummern eindeutig sind — es gibt keine gleichen Schlüssel, deren Reihenfolge erhalten bleiben müsste.

Erwartungshorizont zu Aufgabe d)

Empfehlung: einmal sortieren und danach die sortierte Reihung pflegen — nachts mit Insertionsort (≈ \(10^7\) Vergleiche), tagsüber binär suchen (1,6 Mio. Vergleiche). Gegenüber rein linearer Suche (\(5 \cdot 10^9\) je Tag) spart das über 99 %. Die Empfehlung gilt, solange sich die Daten selten ändern und oft gesucht wird; kämen die neuen Artikel laufend tagsüber, müsste jedes Einfügen sofort an der richtigen Stelle erfolgen.

2

Die besten zehn

13 BEAFB II–III

Ein Sportverein speichert die Punktzahlen aller \(n\) Wettkampfergebnisse einer Saison in int[] a. Für die Vereinszeitung werden nur die besten \(k\) Ergebnisse gebraucht (\(k\) deutlich kleiner als \(n\)). Statt die ganze Reihung zu sortieren, soll die Idee von Selectionsort nur \(k\)-mal angewendet werden.

  1. Entwerfen Sie eine Methode static void besteK(int[] a, int k), die danach an den Indizes 0 bis \(k - 1\) die \(k\) größten Werte absteigend enthält. (4 BE)
  2. Leiten Sie die Anzahl der Vergleiche a[j] > a[maxPos] in Abhängigkeit von \(n\) und \(k\) her. (3 BE)
  3. Berechnen Sie die Vergleichszahl für \(n = 10\,000\) und \(k = 10\) und vergleichen Sie mit vollständigem Sortieren durch Selectionsort. (3 BE)
  4. Diskutieren Sie, in welchen Situationen trotzdem das vollständige Sortieren vorzuziehen ist. (3 BE)

Hinweise

Hinweis zu Aufgabe a)
Selectionsort mit Maximum statt Minimum, aber die äußere Schleife läuft nur \(k\)-mal.
Hinweis zu Aufgabe b)
Im Durchlauf \(i\) läuft j von \(i + 1\) bis \(n - 1\).
Hinweis zu Aufgabe c)
Setzen Sie in die Formel aus b) ein; volles Sortieren: \(\frac{n(n-1)}{2}\).
Hinweis zu Aufgabe d)
Denken Sie an große \(k\), wiederholte Anfragen und weitere Auswertungen.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)
static void besteK(int[] a, int k) {
    for (int i = 0; i < k; i++) {
        int maxPos = i;
        for (int j = i + 1; j < a.length; j++) {
            if (a[j] > a[maxPos]) {
                maxPos = j;
            }
        }
        int h = a[i];
        a[i] = a[maxPos];
        a[maxPos] = h;
    }
}
Erwartungshorizont zu Aufgabe b)

Im Durchlauf \(i\) finden \(n - 1 - i\) Vergleiche statt:

\[\sum_{i=0}^{k-1} (n - 1 - i) = k(n-1) - \frac{(k-1)k}{2} = k \cdot n - \frac{k(k+1)}{2}\]

Für festes \(k\) ist das linear in \(n\): \(O(k \cdot n)\).

Erwartungshorizont zu Aufgabe c)

\(10 \cdot 10\,000 - \frac{10 \cdot 11}{2} = 99\,945\) Vergleiche. Vollständiges Sortieren: \(\frac{10\,000 \cdot 9\,999}{2} = 49\,995\,000\) — etwa 500-mal so viele.

Erwartungshorizont zu Aufgabe d)

Für \(k\) nahe \(n\) nähert sich \(k \cdot n - \frac{k(k+1)}{2}\) dem Wert \(\frac{n(n-1)}{2}\); der Vorteil verschwindet. Werden oft unterschiedliche \(k\) gebraucht (Top 10, Top 50, Platzierung jedes Mitglieds), ist einmal vollständig sortieren günstiger, weil danach jede Anfrage sofort beantwortet ist; zudem erlaubt die sortierte Reihung binäre Suche. Für eine einmalige Liste mit kleinem \(k\) ist besteK klar überlegen. Beide Varianten arbeiten in-place.