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