Aufwandsanalyse

Von experimentellen Verfahren zu mathematischen Beschreibungen

Experimentell bestimmte Laufzeiten haben den Nachteil, dass sie vom benutzen Rechner und den Bedingungen auf dem Rechner (Prozesse, die dort laufen) abhängen. Solche Rechenzeiten sind also nur bedingt aussagekräftig. Erschwerend kommt manchmal hinzu, dass Rechenzeiten bei manchen Problemstellungen so groß werden, dass man sie bis heute noch nicht ermitteln konnte.

Neben experimentellen Methoden benutzt man in der Informatik daher auch mathematische Methoden zur Einschätzung des Laufzeitverhaltens. Man versucht dabei, das Laufzeitverhalten abzuschätzen und abstrahierend zu beschreiben.