Daten in Reihungen
Eine Reihung fasst eine feste Anzahl gleichartiger Werte unter einem Namen zusammen; fast jede Auswertung ist ein Durchlauf mit einer Zählschleife.
Reihung und Index
Feste Länge, ein Datentyp, Zugriff über den Index ab 0. Ein Index außerhalb von 0 … Länge − 1 führt zur ArrayIndexOutOfBoundsException.
int[] a = new int[n];Durchlaufen
Die Zählschleife besucht jedes Element genau einmal; a.length statt fester Zahlen schreiben.
for (int i = 0; i < a.length; i++)Summe, Zählen, Maximum
Akkumulator vor der Schleife: Summe und Zähler mit 0, Maximum mit dem ersten Element.
if (a[i] > max) max = a[i];Zweidimensional
Erst Zeile, dann Spalte; m.length Zeilen, m[0].length Spalten; zwei verschachtelte Schleifen.
m[zeile][spalte]Ganzzahlige Division
Mit int-Werten ist summe / n ganzzahlig: 17 / 4 = 4. Für den genauen Mittelwert (double) summe / n.
Suchen: linear oder binär
Die lineare Suche funktioniert immer; die binäre braucht eine sortierte Reihung und halbiert dafür den Suchbereich mit jedem Vergleich.
Lineare Suche
Ab Index 0 vergleichen, beim ersten Treffer den Index liefern, sonst −1.
Binäre Suche
Mitte des Bereichs links … rechts vergleichen, danach links ← mitte + 1 oder rechts ← mitte − 1; Ende bei links > rechts.
mitte = (links + rechts) / 2Warum die Mitte?
Im ungünstigsten Fall bleibt der größere Teil übrig — nur der Schnitt in der Mitte garantiert höchstens die Hälfte.
Varianten
Erstes Vorkommen oder erster Wert ab einer Schwelle: Treffer merken und links weitersuchen — immer noch logarithmisch.
erg ← mitte; rechts ← mitte − 1Aus \(V(n) = 1 + V(\lfloor n/2 \rfloor)\), \(V(1) = 1\). Beispiel: \(n = 1\,000\,000\) → 20 Vergleiche statt einer Million.
Voraussetzung nennen
Auf unsortierten Daten liefert die binäre Suche still falsche Ergebnisse. Die Reihung muss nach genau dem Merkmal sortiert sein, nach dem gesucht wird.
Sortieren und vergleichen
Die drei einfachen Verfahren sortieren in-place und brauchen im ungünstigsten Fall quadratisch viele Vergleiche; sie unterscheiden sich bei Vertauschungen, Stabilität und vorsortierten Daten.
| Verfahren | Idee | Vergleiche | stabil? | vorsortiert |
|---|---|---|---|---|
| Selectionsort | Minimum des Rests nach vorn tauschen | immer \(\frac{n(n-1)}{2}\) | nein | kein Vorteil |
| Insertionsort | nächstes Element in den sortierten Teil einfügen | \(n-1\) bis \(\frac{n(n-1)}{2}\) | ja | \(O(n)\) |
| Bubblesort | Nachbarn tauschen, Größtes wandert nach hinten | \(\frac{n(n-1)}{2}\), mit Abbruch ab \(n-1\) | ja | \(O(n)\) mit Abbruch |
Doppelte Datenmenge → etwa vierfache Arbeit. Beispiel: \(n = 1000\) → 499 500 Vergleiche.
Umstellungen zählen
Bubblesort-Vertauschungen und Insertionsort-Verschiebungen beseitigen je ein falsch stehendes Paar — gleich viele, aber ein Tausch kostet drei Zuweisungen.
Operationen zählen und O-Notation
Laufzeit wird rechnerunabhängig durch Zählen bestimmt und für große \(n\) nach ihrem Wachstum eingeordnet.
Zählregeln
Sequenz addieren, Schleife: Rumpf \(n\)-mal (Bedingung \(n + 1\)-mal), Verzweigung: teurerer Zweig, verschachtelt: aufsummieren.
Verschachtelte Schleifen
Unabhängige Grenzen multiplizieren sich, eine innere Schleife ab i + 1 ergibt die Dreieckssumme, Halbieren \(\lfloor\log_2 n\rfloor\).
O-Notation
Obere Schranke fürs Wachstum; Konstanten und kleinere Summanden entfallen.
Klassen
Rangfolge von langsam nach schnell wachsend; Verdopplung von \(n\): gleich, +1, ·2, etwas mehr als ·2, ·4, quadriert.
Beispiel: \(3n^2 + 5n + 2 \le 10n^2\) für \(n \ge 1\), also \(\in O(n^2)\). Für kleine \(n\) können Konstanten die Reihenfolge umdrehen.
Hochrechnen
Bei \(O(n^2)\) wird die Zeit bei zehnfacher Datenmenge etwa verhundertfacht; bei \(O(\log n)\) kommen nur gut drei Schritte hinzu.
Speicher und Urteil
Effizienz beurteilen heißt: Zeit und Speicher für die konkreten Daten und ihre Nutzung abwägen.
Speicher einer Reihung
Anzahl der Elemente · Byte je Element (boolean 1, char 2, int 4, double 8); Tabellen zusätzlich je Zeile Kopf und Referenz.
new int[n] ≈ \(4n\) ByteZusatzspeicher
In-place \(O(1)\); Kopie \(O(n)\); Markierungsreihung \(O(W)\) für den Wertebereich; Rekursion kostet Stapelspeicher.
Zeit gegen Speicher
Eine Markierungsreihung macht aus \(O(n^2)\) Vergleichen einen Durchlauf — lohnt sich nur bei kleinem Wertebereich.
Sortieren lohnt ab …
Einmal einfach sortieren und \(k\)-mal binär suchen ist günstiger als \(k\) lineare Suchen etwa ab \(k \approx \frac{n}{2}\).
Urteil in vier Schritten
Kriterium nennen, für den Fall Zahlen oder Klassen bestimmen, Voraussetzungen und Zusatzkosten abwägen, Fazit mit Bedingung formulieren.
Die Regeln, an denen die Punkte hängen
In Klausuren zu Reihungen und Effizienz gehen die meisten Punkte bei Grenzen, beim Zählen und bei unbegründeten Urteilen verloren.
Regel 1 — Grenzen prüfen
Jede Schleife am ersten und letzten Durchlauf testen: < oder <=? Liest der Rumpf a[i + 1], endet die Schleife einen Schritt früher.
Regel 2 — Zählen wie vereinbart
Vorher festlegen, was gezählt wird (Vergleiche, Vertauschungen, Verschiebungen, Bedingungsprüfungen). Formeln mit \(n = 4\) gegenprüfen.
Regel 3 — Fall angeben
Bester, ungünstigster oder durchschnittlicher Fall — ohne Angabe gilt der ungünstigste. Die Eingabe benennen, die ihn erzeugt.
Regel 4 — Urteilen statt behaupten
Mit Klasse und konkreten Zahlen argumentieren, Speicher und Voraussetzungen nennen und das Fazit an eine Bedingung knüpfen („… solange weniger als \(\frac{n}{2}\) Suchen anfallen“).