Algorithmen und Datenstrukturen

Messung des Leistungsverhaltens

  1. Betrachte konkrete Implementierung auf konkrete Hardware
    • misst Laufzeit, Platzverbrauch für repräsentative Eingaben
  2. Berechne Verbrauch an Platz für idealisierte Referenzmaschine
    • Random Access Maschine(RAM)
    • Registermaschine (RM)
    • Turingmaschine (TM)

  3. Bestimme Anzahl(#) bestimmter (teurer) Grundoperationen, etwa 
    • # Vergleiche
    • # Bewegung von Daten(beim Sortieren)
    • # Multiplikation/Division(für numerische Verfahren)
 
2. und 3. Beschreibe Aufwand eines Verfahrens als Funktion der Größe des Inputs (verschieden messbar)

Diskussion