Filter:
01
Code
Reihung anlegen
→ klicken zum Umdrehen
Antwort
int[] a = new int[n];n Plätze, alle mit 0 belegt
02
Code
Tabelle anlegen
→ klicken zum Umdrehen
Antwort
int[][] m = new int[z][s];z Zeilen, s Spalten; Zugriff m[zeile][spalte]
03
Code
Alle Indizes durchlaufen
→ klicken zum Umdrehen
Antwort
for (int i = 0; i < a.length; i++)letzter Index a.length − 1
04
Code
Mitte der binären Suche
→ klicken zum Umdrehen
Antwort
int mitte = (links + rechts) / 2;überlaufsicher: links + (rechts − links) / 2
05
Code
Grenzen verschieben
→ klicken zum Umdrehen
Antwort
links = mitte + 1; / rechts = mitte - 1;die Mitte ist nach dem Vergleich erledigt
06
Code
Tauschen
→ klicken zum Umdrehen
Antwort
int h = a[i]; a[i] = a[j]; a[j] = h;ohne Hilfsvariable geht ein Wert verloren
07
Code
Markierungsreihung
→ klicken zum Umdrehen
Antwort
boolean[] gesehen = new boolean[W + 1];ein Platz je möglichem Wert 0 … W
08
Formel
Gültige Indizes
→ klicken zum Umdrehen
Antwort
\(0 \le i \le n-1\)bei a.length = \(n\)
09
Formel
Binäre Suche: Aufwand
→ klicken zum Umdrehen
Antwort
\(\lfloor\log_2 n\rfloor + 1\)Vergleiche im ungünstigsten Fall
10
Formel
Rekursionsgleichung der binären Suche
→ klicken zum Umdrehen
Antwort
\(V(n) = 1 + V(\lfloor n/2 \rfloor)\)mit \(V(1) = 1\)
11
Formel
Dreieckssumme
→ klicken zum Umdrehen
Antwort
\(\frac{n(n-1)}{2}\)Selectionsort; innere Schleife ab i + 1
12
Formel
O-Notation
→ klicken zum Umdrehen
Antwort
\(T(n) \le c \cdot f(n)\)für alle \(n \ge n_0\)
13
Formel
Speicher einer Reihung
→ klicken zum Umdrehen
Antwort
\(n \cdot s\) Bytes = Byte je Element (int 4, double 8)
14
Formel
Sortieren lohnt ab
→ klicken zum Umdrehen
Antwort
\(k \approx \frac{n}{2}\) Suchenbei einfachem Sortieren und binärer Suche
15
Begriff
Index
→ klicken zum Umdrehen
Antwort
Die Platznummer eines Elements in einer Reihung, beginnend bei 0.
16
Begriff
Lineare Suche
→ klicken zum Umdrehen
Antwort
Elemente der Reihe nach vergleichen; erster Treffer oder −1. Funktioniert auf jeder Reihung.
17
Begriff
Binäre Suche
→ klicken zum Umdrehen
Antwort
Suchbereich einer sortierten Reihung in jedem Schritt halbieren.
18
Begriff
Invariante der binären Suche
→ klicken zum Umdrehen
Antwort
Kommt x vor, liegt es immer im Bereich links … rechts.
19
Begriff
Selectionsort
→ klicken zum Umdrehen
Antwort
Minimum des unsortierten Rests suchen und an den Anfang des Rests tauschen.
20
Begriff
Insertionsort
→ klicken zum Umdrehen
Antwort
Das nächste Element in den sortierten linken Teil einfügen; größere rücken nach rechts.
21
Begriff
Bubblesort
→ klicken zum Umdrehen
Antwort
Benachbarte Elemente vertauschen, bis ein Durchlauf ohne Vertauschung bleibt.
22
Begriff
Stabil
→ klicken zum Umdrehen
Antwort
Gleiche Schlüssel behalten beim Sortieren ihre ursprüngliche Reihenfolge.
23
Begriff
In-place
→ klicken zum Umdrehen
Antwort
Ein Verfahren braucht außer der Eingabe nur Speicher, der nicht mit \(n\) wächst.
24
Begriff
Laufzeitfunktion
→ klicken zum Umdrehen
Antwort
\(T(n)\): Zahl der Schritte eines Algorithmus in Abhängigkeit von der Problemgröße \(n\).
25
Begriff
Ungünstigster Fall
→ klicken zum Umdrehen
Antwort
Die Eingabe der Länge \(n\), für die ein Verfahren am meisten Schritte braucht; gilt garantiert.
26
Begriff
Wachstumsklasse
→ klicken zum Umdrehen
Antwort
Einordnung nach dem Wachstum für große \(n\): konstant, logarithmisch, linear, \(n \log n\), quadratisch, exponentiell.
27
Begriff
Quadratisches Wachstum
→ klicken zum Umdrehen
Antwort
Doppelte Datenmenge bedeutet etwa vierfache Arbeit.
28
Begriff
Logarithmisches Wachstum
→ klicken zum Umdrehen
Antwort
Doppelte Datenmenge bedeutet nur einen Schritt mehr.
29
Begriff
Zusatzspeicher
→ klicken zum Umdrehen
Antwort
Speicher, den ein Algorithmus neben der Eingabe anlegt, z. B. eine Kopie mit \(O(n)\).
30
Begriff
Zeit-Speicher-Abwägung
→ klicken zum Umdrehen
Antwort
Mehr Speicher (z. B. Markierungsreihung) spart Rechenzeit — lohnt sich nur, wenn der Speicher verfügbar ist.
Keine Karten in dieser Auswahl.
Geh den Stapel dreimal durch: erst alle Karten, dann nur Code und Formeln, zuletzt nur die ungelernten. Schreib bei Code-Karten die Zeile auf, bevor du umdrehst — und prüfe jede Formel an einem eigenen Beispiel, etwa \(n = 8\).