Welche Eigenschaften interessieren uns bei Algorithmen?
Korrektheit, Laufzeit, Speicherplatz, Kommunikationszeit, Güte u.a.
Warum ist es keine gute Idee, zum Bewerten von Algorithmen deren Laufzeiten zu messen?
Laufzeiten messen und vergleichen bringt nichts aufgrund
unterschiedlich schneller Hardware
unterschiedlich guter Compiler
unterschiedlicher Betriebssysteme
Laufzeitumgebungen
unterschiedlichen Eingabedarstellungen
Datenstrukturen usw
Wie bewerten bzw. vergleichen wir Algorithmen?
• Wir verwenden idealisierte Rechenmodelle wie die Registermaschine (Random Access Machine, RAM) festgelegter Befehlssatz (Assembler-ähnlich), abzählbar unendlich viele Speicherzellen.
Die Laufzeit ist dann die Anzahl ausgeführter RAM-Befehle, der Speicherbedarf ist die
Anzahl der benötigten Speicherzellen.
• Bei den einzelnen Problemstellungen ermitteln wir charakteristische Parameter. Beim Sortieren sind dies bspw. die Anzahl der Schlüsselvergleiche bzw. Vertauschungen, bei
arithmetischen Problemen bspw. die Anzahl der Additionen oder Multiplikationen.
Laufzeit und Speicherbedarf sind in der Regel abhängig von der Größe der Eingabe.
Last changed20 days ago