Komplexität von Algorithmen

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)