Kurs:Algorithmen und Datenstrukturen/Kapitel 3
Dieses Kapitel gehoert zum Kurs Algorithmen und Datenstrukturen des Fachbereichs Informatik.
Suchen in Arrays und Listen
[Bearbeiten]- Kurze Beschreibung dessen, was in diesem Kapitel alles vorkommen wird
Asymptotische Analyse
[Bearbeiten]- Welche operationen werden gezaehlt
- Was fuer Elemente werden gesucht, Haeufigkeit, Reihenfolge
Suchen in unsortierten Arrays
[Bearbeiten]- Beschreibung des Algorithmus
- Average-Case Analyse
- Andere Suchrichtungen bringen nichts
Suchen in sortierten Arrays
[Bearbeiten]- Beschreibung des Algorithmus (binaere Suche)
- Average-Case Analyse
- Ternaere Suche als Beispiel
- Asymptotisches Verhalten gleich, kommt also nicht darauf an
Suchen in Listen
[Bearbeiten]- Unterschied zu Arrays, nur sequenzielle Suche moeglich
- Kompensation mit Skip-Lists, Nachteile
- Move-to-Front Strategien, ganz nach vorne oder nur ein Schritt
- Asymptotische Analyse