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.
| 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)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
P1: Faktor 2 je Verdopplung → linear, \(O(n)\). P2: Faktor 4 je Verdopplung → quadratisch, \(O(n^2)\). P3: je Verdopplung kommt ein fester Betrag (0,3 ms) hinzu → logarithmisch, \(O(\log n)\).
Erwartungshorizont zu Aufgabe b)
Dreimal verdoppeln: P1 \(160 \cdot 2^3 = 1280\) ms ≈ 1,3 s; P2 \(32\,000 \cdot 4^3 = 2\,048\,000\) ms ≈ 34 min; P3 \(3{,}9 + 3 \cdot 0{,}3 = 4{,}8\) ms.
Erwartungshorizont zu Aufgabe c)
P1 lineare Suche (gesuchter Wert fehlt oder steht am Ende), P2 Insertionsort (Daten umgekehrt sortiert), P3 binäre Suche (Wert fehlt; die Reihung muss sortiert sein).
Erwartungshorizont zu Aufgabe d)
Messzeiten hängen von Rechner, Sprache und Auslastung ab und schwanken; bei kleinen \(n\) überdecken konstante Anteile (Programmstart, Speicherzugriffe) das Wachstum. Messungen liefern nur Stichproben für einzelne \(n\) — die Klasse muss durch Zählen der Operationen begründet werden; Messungen können sie nur bestätigen.
O-Notation präzise
14 BEAFB II–IIIDie O-Notation ist definiert durch: \(T(n) \in O(f(n))\), wenn es Konstanten \(c > 0\) und \(n_0\) gibt, sodass \(T(n) \le c \cdot f(n)\) für alle \(n \ge n_0\) gilt.
static int kennzahl(int[] a) {
int n = a.length;
int s = 0;
for (int i = 0; i < n; i++) { // Teil 1
s = s + a[i];
}
for (int i = 0; i < n; i++) { // Teil 2
for (int k = 1; k < n; k = k * 2) {
s = s + a[i] % k;
}
}
return s;
}- Zeigen Sie mithilfe der Definition, dass \(T(n) = 2n^2 + 10n + 50\) in \(O(n^2)\) liegt. Geben Sie geeignete Werte für \(c\) und \(n_0\) an. (3 BE)
- Widerlegen Sie die Behauptung \(n^2 \in O(n)\). (3 BE)
- Analysieren Sie die Methode
kennzahl: Bestimmen Sie für \(n = 16\) die Zahl der Additionen und ordnen Sie die Laufzeit allgemein einer Wachstumsklasse zu. (4 BE) - Beurteilen Sie die Aussage: „Algorithmus A mit \(1000 \cdot n \cdot \log_2 n\) Schritten ist immer besser als Algorithmus B mit \(n^2\) Schritten, weil \(O(n \log n)\) die bessere Klasse ist.“ (4 BE)
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
k für \(n = 16\) an?Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
Für \(n \ge 1\) gilt \(n \le n^2\) und \(1 \le n^2\), also \(2n^2 + 10n + 50 \le 2n^2 + 10n^2 + 50n^2 = 62n^2\). Mit \(c = 62\) und \(n_0 = 1\) ist die Definition erfüllt. (Auch z. B. \(c = 3\), \(n_0 = 15\) ist möglich, denn \(10n + 50 \le n^2\) für \(n \ge 15\).)
Erwartungshorizont zu Aufgabe b)
Angenommen, es gäbe \(c > 0\) und \(n_0\) mit \(n^2 \le c \cdot n\) für alle \(n \ge n_0\). Division durch \(n > 0\) ergibt \(n \le c\) für alle \(n \ge n_0\) — für \(n = \max(n_0, \lceil c \rceil + 1)\) ist das falsch. Also liegt \(n^2\) nicht in \(O(n)\).
Erwartungshorizont zu Aufgabe c)
Teil 1: 16 Additionen. Teil 2: k durchläuft 1, 2, 4, 8 — vier Werte, also \(16 \cdot 4 = 64\) Additionen. Zusammen 80. Allgemein: \(n + n \cdot \lceil\log_2 n\rceil\) Additionen; der zweite Summand dominiert: \(T(n) \in O(n \log n)\). Hintereinander stehende Teile addieren sich, und die Summe gehört zur Klasse des größeren Teils.
Erwartungshorizont zu Aufgabe d)
Für \(n = 1000\): A ≈ \(1000 \cdot 1000 \cdot 10 = 10^7\), B = \(10^6\) — B ist zehnmal schneller. Gleichstand bei \(n = 1000 \log_2 n\), also etwa \(n \approx 13\,750\). Für \(n = 10^6\): A ≈ \(2 \cdot 10^{10}\), B = \(10^{12}\) — A ist 50-mal schneller. Die Aussage ist also nur asymptotisch richtig: Die bessere Klasse gewinnt ab einer bestimmten Größe und dann immer deutlicher; für kleine \(n\) kann der große konstante Faktor A langsamer machen. Welcher Algorithmus besser ist, hängt von den tatsächlich auftretenden Datenmengen ab.