Komplexität von Algorithmen

Id: komplex.tex,v 1.2 2004/10/28 05:25:42 waldmann Exp

Wie gut ist ein Algorithmus?

• Ressourcen-Verbrauch (Rechenzeit/Speicherplatz/...)?
• Für eine spezielle Eingabe? -- Besser: Mengen von ähnlichen (= gleich großen) Eingaben betrachten.
• Ressourcen für besten, mittleren, schlechtesten Fall.
• Betrachten der Verbrauchsfunktion:

  bildet Eingabegröße ab auf (minimale, durchschnittliche, maximale) Kosten aller Rechnungen für alle Eingaben dieser Größe

• Maschinen-unabhängige Aussagen durch Betrachtung des (asymptotischen) Wachstums, d. h. ignoriere:
  • Unregelmäßigkeiten für kleine Eingaben
  • konstante Faktoren (für alle Eingaben)

Beispiele: alle linearen Funktionen wachsen ähnlich, alle quadratischen Funktionen wachsen ähnlich, etc.