Kriterien für ein Urteil
„Effizient“ heißt: wenig Rechenzeit und wenig Speicher für die konkrete Aufgabe. Ein Urteil verbindet deshalb die Eigenschaften der Verfahren mit den Daten und ihrer Nutzung.
| Verfahren | bester Fall | ungünstigster Fall | Zusatzspeicher | Besonderheit |
|---|---|---|---|---|
| lineare Suche | \(O(1)\) | \(O(n)\) | \(O(1)\) | jede Reihung |
| binäre Suche | \(O(1)\) | \(O(\log n)\) | \(O(1)\) | nur sortiert |
| Selectionsort | \(O(n^2)\) | \(O(n^2)\) | \(O(1)\) | höchstens \(n - 1\) Vertauschungen, nicht stabil |
| Insertionsort | \(O(n)\) | \(O(n^2)\) | \(O(1)\) | stabil, schnell bei fast sortierten Daten |
| Bubblesort mit Abbruch | \(O(n)\) | \(O(n^2)\) | \(O(1)\) | stabil, viele Vertauschungen |
- Wachstumsklasse:entscheidet bei großen \(n\) — gemessen im ungünstigsten Fall, weil er garantiert gilt.
- Daten:Wie groß ist \(n\)? Sind die Daten vorsortiert? Wie groß ist der Wertebereich?
- Nutzung:einmal oder sehr oft? Ein teurer Vorbereitungsschritt (z. B. Sortieren) verteilt sich auf viele Anfragen.
- Speicher:reicht der Arbeitsspeicher für eine Kopie oder eine Markierungsreihung?
- Weitere Kriterien:Konstanten bei kleinem \(n\), teure Schreibzugriffe, Stabilität, Verständlichkeit des Codes.
Links \(k\) lineare Suchen, rechts einmal einfach sortieren und \(k\) binäre Suchen (ungünstigster Fall, ohne Abrunden). Wann ist links mehr Arbeit?
Alle Summanden mit \(k\) auf die linke Seite bringen.
Durch die Klammer teilen; sie ist für \(n \ge 4\) positiv.
Für große \(n\) ist \(\log_2 n\) gegen \(n\) vernachlässigbar. Beispiel \(n = 100\,000\): Sortieren lohnt sich erst ab etwa 50 000 Suchen.
Urteilen an Fällen
Lies den Fall, tippe auf den Kandidaten, den du für effizienter hältst, und decke dann mit ▶ die Aufwände auf. Die Balken sind logarithmisch: Jede Markierung bedeutet das Tausendfache. Spiele alle sechs Fälle durch.
Halte fest: Die bessere Wachstumsklasse gewinnt nur, wenn ihre Voraussetzungen erfüllt sind und sich ihr Mehraufwand (Sortieren, Zusatzspeicher) über die Nutzung auszahlt.
- 1. Kriterium:nennen, woran gemessen wird — Vergleiche, Schreibzugriffe oder Speicher.
- 2. Anwenden:für den Fall konkrete Zahlen oder Klassen bestimmen.
- 3. Abwägen:Voraussetzungen und Zusatzkosten prüfen (sortiert? Speicher frei? wie oft?).
- 4. Fazit:eine klare Entscheidung mit ihrer Grenze: „… solange weniger als \(\frac{n}{2}\) Suchen anfallen“.
Effizienz beurteilen = Wachstumsklasse im ungünstigsten Fall und Daten (Größe, Vorsortierung, Wertebereich) und Nutzung (einmal oder oft) und Speicher
Allgemeine Hinweise
Eine Zahl ist noch kein Urteil
„Braucht 190 Vergleiche“ beantwortet keine Beurteilungsfrage. Erst der Vergleich mit der Alternative und eine Begründung für die konkrete Situation machen daraus ein Urteil.
Den Sonderfall der Daten nutzen
Vorsortierte Daten, kleine Wertebereiche oder seltene Änderungen sind oft der Schlüssel: Sie machen ein sonst schwächeres Verfahren zum besten.
Voraussetzungen mitprüfen
Die binäre Suche braucht sortierte Daten, die Markierungsreihung einen kleinen Wertebereich. Wer nur die Klasse vergleicht, übersieht die versteckten Kosten.