Rechenaufwand

Zur Ausführung eines Algorithmus bzw. eines entsprechenden Programms auf einem Computer wird neben Speicherplatz v.a. Rechenzeit benötigt. Definieren wir „eine Zeiteinheit“ (= ein Elementarschritt, z.B. eine Addition oder ein Vergleich), so können wir den Rechenzeitverbrauch bzw. Rechenaufwand eines Algorithmus zur Lösung eines Problems bzw. einer Modellinstanz ermitteln. Dies kann durch Abzählen der erforderlichen Elementarschritte geschehen. Interessanter als der Rechenaufwand für jede einzelne Instanz sind globale Aussagen über den Rechenaufwand eines Algorithmus zur Lösung von Problemen eines bestimmten Typs, wie sie in der Komplexitätstheorie gewonnen werden.

<< vorhergehender Begriff

nächster Begriff >>

Recepisse Postal

Rechengrößen