IT – Suchverfahren

Suche in ungeordneten linearen Listen

Sequentielle Suche

  • durchlaufe Liste sequentiell bis Schlüssel gefunden oder Listenende erreicht ist
  • linearer Suchaufwand: O(n)

Suche in geordneten linearen Listen

Sequentielle Suche

  • durchlaufe Liste  (aufsteigend) solange Suchschlüssel größer aktueller Schlüssel und Listenende nicht erreicht
  • linearer Suchaufwand: O(n)

Binäre Suche

  • V1
    • Intervallunterteilung bis Intervallgröße = 1
    • Aufwand: O(log²n)
    • kein Abbruch, selbst wenn Schlüssel gefunden wird
  • V2
    • Divide & Conquer
    • auf Pos. bezogen mittlere Element suchen und mit Schlüssel vergleichen
    • anschließend ggfs. Teilbereich weiter durchsuchen
    • zmin = 1 (sofortiger Fund)
    • zmax = h (Höhe des Baumes) –> Herleitung für Examen!!! (folgt)
    • Aufwand worst-case: O(logn)

 Sprungsuche / Intervallsuche

  • sortierter Datenbestand in Sprüngen überqueren
  • Abschnitt lokalisieren
  • einfache Sprungsuche
    • konstante Sprungweite
    • sequentielle Suche im Sprungbereich
  • binäre
    • konstante Sprungweite
    • binäre Suche im Sprungbereich
  • Aufwand: O(√n) = O(n^½) – zwischen sequentieller und binärer Suche

IT – Stack / Queue

Stack

  • Kellerspeicher, Stapel, LIFO (Last In First Out)
  • Liste, bei der alle Änderungen (Einfügen, Löschen) nur am Ende Top vorgenommen werden
  • Funktionen:
    • Create – erzeugt leeren Stack
    • Init – initialisiert Stack als leeren Stack
    • Push – fügt neues Element hinzu
    • Pop – entfent aktuelles Element
    • Top – zeigt aktuelles Element an
    • Empty – fragt ab, ob Stack leer ist

FIFO

  • Schlange, Queue, Warteschlange, FIFO ( First In First Out)
  • Funktionen:
    • Create – erzeugt leere Schlange
    • Init – initialisiert Schlange als leere Schlange
    • Enqueue – fügt Element ans Ende der Schlange hinzu
    • Dequeue – entfernt Element; das am längsten in der Schlange verweilt
    • Front – zeigt 1. Element
    • Empty – prüft ob Schlange leer ist

 

Zoo Neuwied

Oben erwähnter Zoo erwartet tatsächlich, dass man vor Veröffentlichung der Bilder eine Genehmigung einholt… das macht nicht mal der Kölner Zoo.