Hier sind die 12 häufigsten Fehler in Klausuren zu Reihungen, Suchen, Sortieren und Effizienz. Lies sie durch — wer einen Fehler kennt, macht ihn seltener. Die meisten passieren an Schleifengrenzen und beim Zählen.
Die 12 häufigsten Fehler
1Schleife läuft einen Platz zu weit
i <= a.length statt i < a.length
So wird oft gearbeitet: Zum Aufsummieren von int[] a = new int[8];:
for (int i = 0; i <= a.length; i++) {
summe = summe + a[i]; // i = 8: Abbruch
}Richtig ist: Letzter gültiger Index ist a.length − 1 = 7; der Zugriff auf a[8] bricht mit ArrayIndexOutOfBoundsException ab.
for (int i = 0; i < a.length; i++) {
summe = summe + a[i];
}Zählschleife über eine Reihung: Start bei 0, Bedingung i < a.length.
2Maximum mit 0 begonnen
int max = 0; bei negativen Werten
So wird oft gearbeitet: Für die Tiefstwerte {-4, -9, -2} wird mit max = 0 gestartet — Ergebnis 0.
Richtig ist: Das Maximum beginnt mit dem ersten Element: int max = a[0];, die Schleife dann ab Index 1. Ergebnis −2.
Startwert eines Maximums oder Minimums ist ein Element der Reihung, keine feste Zahl.
3Zeile und Spalte vertauscht
m[spalte][zeile] und falsche Längen
So wird oft gearbeitet: Für new int[3][5] läuft die innere Schleife bis m.length — sie endet nach 3 statt nach 5 Spalten.
Richtig ist: m.length ist die Zahl der Zeilen (3), m[z].length die Zahl der Spalten (5). Zugriff immer m[zeile][spalte].
Außen die Zeilen mit m.length, innen die Spalten mit m[z].length.
4Lineare Suche gibt zu früh auf
else return -1; in der Schleife
So wird oft gearbeitet: Im Rumpf steht if (a[i] == x) return i; else return -1; — nach dem ersten Element ist Schluss.
Richtig ist: Erst wenn alle Elemente geprüft sind, steht fest, dass x fehlt. return -1; gehört hinter die Schleife.
Ein „nicht gefunden“ steht immer nach der Schleife.
5Binäre Suche nach dem falschen Schlüssel
sortiert nach Signatur, gesucht nach Autor
So wird oft gearbeitet: Die Bücherliste ist nach Signatur sortiert; trotzdem wird binär nach dem Autor gesucht.
Richtig ist: Die binäre Suche verlangt Sortierung nach genau dem Merkmal, nach dem gesucht wird. Sonst liefert sie still falsche Ergebnisse — ohne Fehlermeldung.
Vor jeder binären Suche prüfen: sortiert — und zwar nach dem Suchschlüssel?
6Suchbereich wird nicht kleiner
links = mitte statt mitte + 1
So wird oft gearbeitet:
} else if (a[mitte] < x) {
links = mitte; // bei links = 4, rechts = 5 bleibt alles gleich
}Richtig ist: Die Mitte ist nach dem Vergleich erledigt: links = mitte + 1 bzw. rechts = mitte - 1. Sonst bleibt ein Bereich mit zwei Elementen unverändert und die Schleife läuft endlos.
Nach jedem Vergleich muss der Bereich um mindestens ein Element schrumpfen.
7Minimum als Wert statt als Index
Selectionsort merkt sich den Wert
So wird oft gearbeitet: In Selectionsort wird min = a[j]; gespeichert — beim Tauschen fehlt dann die Position.
Richtig ist: Gemerkt wird der Index: if (a[j] < a[minPos]) minPos = j;, danach a[i] mit a[minPos] tauschen.
Wer tauschen will, braucht die Position, nicht nur den Wert.
8Schleifenkopf falsch gezählt
Bedingung \(n\)- statt \((n + 1)\)-mal
So wird oft gearbeitet: Für for (int i = 0; i < n; i++) werden \(n\) Bedingungsprüfungen gezählt.
Richtig ist: Der Rumpf läuft \(n\)-mal, die Bedingung wird aber \((n + 1)\)-mal geprüft — die letzte, falsche Prüfung beendet die Schleife.
Vorher festlegen, was gezählt wird — und den Randfall \(n = 0\) prüfen.
9Innere Grenze übersehen
\(n^2\) statt \(\frac{n(n-1)}{2}\)
So wird oft gearbeitet: Für for (i …) for (int j = i + 1; j < n; j++) werden „zwei Schleifen, also \(n \cdot n\)“ Durchläufe angegeben: für \(n = 10\) also 100.
Richtig ist: Die innere Schleife läuft nur \(n - 1 - i\)-mal: \(9 + 8 + \ldots + 1 = 45\). Die Klasse bleibt \(O(n^2)\), die Zahl ist aber halb so groß.
Grenzen der inneren Schleife lesen und für \(n = 4\) gegenprüfen.
10Konstanten in der O-Notation
\(O(3n^2 + n)\) oder „\(O(n)\) ist immer schneller“
So wird oft gearbeitet: Angegeben wird \(O(\frac{n^2}{2} + n)\); außerdem wird behauptet, ein \(O(n)\)-Verfahren sei für jedes \(n\) schneller als ein \(O(n^2)\)-Verfahren.
Richtig ist: In der Klasse stehen keine Konstanten und keine kleineren Summanden: \(O(n^2)\). Die Klasse beschreibt das Wachstum für große \(n\) — bei kleinen \(n\) kann ein \(O(n^2)\)-Verfahren mit kleiner Konstante gewinnen.
O-Notation: nur der am schnellsten wachsende Term, ohne Faktor — und nur eine Aussage für große \(n\).
11Speicher falsch abgeschätzt
Referenz mit Objekt verwechselt, Zeilen vergessen
So wird oft gearbeitet: new String[1000] wird mit dem Speicher von 1000 Texten gleichgesetzt; new int[1000][1000] mit 4000 Byte.
Richtig ist: Eine String-Reihung enthält nur Referenzen (4–8 Byte); die Texte kommen hinzu, sobald sie zugewiesen werden. Die Tabelle hat \(10^6\) Elemente: 4 000 000 Byte.
Speicher = Anzahl der Elemente · Byte je Element; bei Tabellen Zeilen · Spalten.
12Urteil ohne Bedingung
„Binär ist besser.“ — auch für eine einzige Suche
So wird oft gearbeitet: Für eine einzelne Suche in 20 unsortierten Werten wird empfohlen, erst zu sortieren und dann binär zu suchen, „weil binär schneller ist“.
Richtig ist: Sortieren kostet hier 190 Vergleiche, die lineare Suche höchstens 20. Sortieren lohnt sich erst ab etwa \(\frac{n}{2}\) Suchen; ein Urteil muss Kosten, Nutzung und Voraussetzungen nennen.
Ein Effizienzurteil nennt Kriterium, Zahlen für den Fall und die Bedingung, unter der es gilt.