Dein Fortschritt:
0 / 0 Aufgaben
1
Ausleihe in der Schulbibliothek
AFB I–IIDie Schulbibliothek speichert die Nummern der 1 500 ausgegebenen Leseausweise in einer Reihung. Bei jeder Ausleihe wird geprüft, ob die Nummer gültig ist. Zur Wahl stehen die lineare Suche auf der unsortierten Reihung und die binäre Suche auf einer sortierten Reihung.
- Geben Sie für beide Verfahren die Zahl der Vergleiche im besten und im ungünstigsten Fall an.
- Erläutern Sie, warum die lineare Suche bei einer gültigen Nummer im Mittel etwa \(\frac{n+1}{2}\) Vergleiche braucht, und nennen Sie die Voraussetzung dafür.
- Durch eine Kooperation mit zwei Nachbarschulen wächst die Zahl der Ausweise auf 6 000. Schätzen Sie ab, wie sich die Zahlen aus a) für den ungünstigsten Fall ändern.
- Skizzieren Sie in einem gemeinsamen Diagramm die Zahl der Vergleiche im ungünstigsten Fall beider Verfahren in Abhängigkeit von \(n\) für \(1 \le n \le 32\).
Hinweise
Hinweis zu Aufgabe a)
Bester Fall: Wo muss der Wert stehen? Ungünstigster: Wann ist der längste Weg nötig?
Hinweis zu Aufgabe b)
Jede Position 0 … n − 1 kostet eine andere Zahl von Vergleichen; bilden Sie den Mittelwert.
Hinweis zu Aufgabe c)
6 000 = 4 · 1 500 — das sind zwei Verdopplungen.
Hinweis zu Aufgabe d)
Die binäre Suche springt immer bei Zweierpotenzen um eine Stufe.