Dein Fortschritt:
0 / 0 Aufgaben
1
Drei Programme im Test
12 BEAFB I–IIEine Softwarefirma testet drei Programme P1, P2 und P3 mit wachsenden Datenmengen \(n\). Jedes Programm verwendet genau eines der Verfahren lineare Suche, binäre Suche oder Insertionsort.
Gemessene Laufzeiten in Millisekunden (ungünstigster Fall, Mittel aus 20 Läufen)
| n | 1 000 | 2 000 | 4 000 | 8 000 |
|---|---|---|---|---|
| P1 | 20 | 40 | 80 | 160 |
| P2 | 500 | 2 000 | 8 000 | 32 000 |
| P3 | 3,0 | 3,3 | 3,6 | 3,9 |
- Ermitteln Sie aus den Messwerten die Wachstumsklasse jedes Programms und begründen Sie Ihre Zuordnung mit dem Verhalten bei Verdopplung von \(n\). (4 BE)
- Schätzen Sie die Laufzeiten der drei Programme für \(n = 64\,000\) ab. (3 BE)
- Ordnen Sie den Programmen die Verfahren lineare Suche, binäre Suche und Insertionsort zu und nennen Sie jeweils die Voraussetzung, unter der die Messung den ungünstigsten Fall zeigt. (3 BE)
- Erläutern Sie, warum Laufzeitmessungen allein kein sicheres Urteil über die Wachstumsklasse erlauben. (2 BE)
Hinweise
Hinweis zu Aufgabe a)
Bilden Sie für jede Zeile die Quotienten aufeinanderfolgender Werte — oder bei P3 die Differenzen.
Hinweis zu Aufgabe b)
64 000 ist 8 000 dreimal verdoppelt.
Hinweis zu Aufgabe c)
Welche Eingabe ist für jedes Verfahren am ungünstigsten?
Hinweis zu Aufgabe d)
Denken Sie an Rechner, Messschwankungen und kleine \(n\).