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