Kurs:Algorithmen und Datenstrukturen/Kapitel 3

Aus Wikiversity
Zur Navigation springen Zur Suche springen

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