Educational Cards
Learn from video content, text, and interactive tasks
Filters
Vergleiche und Vertauschungen
Analysiere getrennt: Vergleiche (Lesen) und Schreib-/Tauschkosten. Selection Sort: viele...
Implementierung: naive Suche
Implementiere die naive Suche und gib den ersten Index oder -1 zurück. ## Wo gebraucht...
Java String und indexOf
In Java sucht String.indexOf naiv oder mit JVM-Optimierungen. Für Lehre zählt der Algorithmus,...
KMP-Idee: Präfixfunktion
KMP vorberechnet eine longest-prefix-suffix-Tabelle (pi) für das Muster. Bei Mismatch springt der...
Regex grob und Kosten
Regex sind mächtig, aber können backtracken und teuer werden. Für festes exaktes Muster sind KMP...
Naive Textsuche
Naive Suche prüft für jede Textposition, ob das Muster passt. Bei Mismatch verschiebt sie um 1....
Komplexität der naiven Suche
Seien n Textlänge und m Musterlänge. Naive Suche ist O(n m) im Worst Case (z.B. aaaa... vs...
Offene Adressierung grob
Offene Adressierung speichert Einträge in der Tabelle selbst und sucht bei Kollision alternative...
Lastfaktor und Rehash
Der Lastfaktor ist n / Kapazität. Überschreitet er eine Schwelle, reallociert die Tabelle (Rehash):...
Kleine Implementierung: Bucketindex
Bucketindex aus hashCode und Tabellenlänge: typisch (hash & 0x7fffffff) % capacity oder bit...
Hashing: Idee und Buckets
Hashing bildet Schlüssel auf Bucketindizes ab. Erwartete Zugriffszeit ist O(1), wenn die...
Kollisionen: Chaining
Chaining speichert kollidierende Einträge in einer Liste (oder einem Baum) pro Bucket. Einfügen...