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 – Komplexitäten

Eigenschaften eines Programms

  • Effizienz
  • Korrektheit
  • Zuverlässigkeit
  • Robustheit

Zeitkomplexität: Aufwand an Rechenzeit (in Schritten gemessen)

Unterscheidung:

  • worst-case
  • best-case
  • average-case

Beschreibung:

  • exakt: Zählfunktion T: N -> N; n ∈ N
  • asymptotisch: Angabe einer Vgl.größe (Komplexitätsklasse)

Speicherplatzkomplexität: Umfang des zu reservierenden Speicherplatzes

Komplexitätsklassen

obere Schranke

O(f(n)) := { g: N -> N | ∃c ∈ R, c >0: ∃ n0 ∈ N: ∀n >= n0: g(n) ≤ c * f(n)}

untere Schranke

Ω(f(n)) := { g: N -> N | ∃c ∈ R, c >0: ∃ n0 ∈ N: ∀n >= n0: g(n) ≥ c * f(n)}

 

O( 1 ) – konstant

O( log2n ) – logarithmisch – Bsp. binäre Suche

O( n ) – linear – Bsp. sequentielle Suche

O( n * log2n ) – n log n – Bsp. gute Sortierverfahren

O( n² ) – quadratisch

O( n³ ) – kubisch

O( 2^n ) – exponentiell

 

Faustregeln

  • Fallunterscheidung: Kosten der Anweisung + Kosten der teuersten Alternative
  • Schleife: Zahl der Durchläufe * Kosten der teuersten Durchführung
  • Rekursion: Anzahl der Aufrufe * Kosten der teuersten Durchführung
  • Vergleich versch. Operationen: Kosten der einzelnen Operationen bestimmen