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