Nächste Seite: Komplexität - Beispiel
Aufwärts: Berechenbarkeit, Komplexität (24. 10.
Vorherige Seite: Berechenbarkeit, Komplexität (24. 10.
Id: komplex.tex,v 1.1 2003/10/23 16:27:18 joe Exp
Wie gut ist ein Algorithmus?
- Wieviel Rechenzeit/Speicherplatz benötigt er?
- Für eine spezielle Eingabe? --
Besser: Mengen von ähnlichen (= gleich großen) Eingaben betrachten.
- Resourcenverbrauch im besten, mittleren, schlechtesten Fall.
- Betrachten der Verbrauchsfunktion
(bildet Eingabegröße auf Kosten ab).
- Maschinen-unabhängige Aussagen
durch Betrachtung des (asymptotischen) Wachstums, d. h. ignoriere:
- Unregelmäßigkeiten für kleine Eingaben
- konstante Faktoren (für alle Eingaben)
Johannes Waldmann
2004-01-30