Dein Fortschritt:
0 / 0 Aufgaben
1
Preisabfragen im Online-Shop
12 BEAFB IIEin 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.
- 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)
- Begründen Sie, warum ab der zweiten Nacht Insertionsort statt Selectionsort die bessere Wahl ist, und schätzen Sie seinen Aufwand ab. (3 BE)
- Erläutern Sie den Speicherbedarf der Strategien und ob die Stabilität des Sortierverfahrens hier eine Rolle spielt. (2 BE)
- 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.