Einleitung

Es gibt eine Vielzahl von Werkzeugen, die den Prozeß des Programmierens unterstützen (z.B. Transformationssysteme, Automatisierung von Programmentwicklungsmethoden). Allen diesen Werkzeugen ist gemeinsam, daß sie eine Menge von Regeln enthalten. Die sukzessive Anwendung dieser Regeln auf eine formale Spezifikation soll zu einer effizienten und korrekten Implementierung der Spezifikation führen. In der Tat stellen diese Werkzeuge die Korrektheit einer Implementierung bezüglich ihrer Spezifikation sicher. Andererseits stellen diese Werkzeuge nicht sicher, daß eine Implementierung effizient ist. Normalerweise garantieren nur wenige Regeln und Methoden eine Verbesserung der Effizienz. Oft haben die Regeln und Methoden die Eigenschaft, daß sich bei ihrer Anwendung die Zeiteffizienz eines Programms verbessert. In manchen Fällen kann sich aber auch die Effizienz verschlechtern. Wenn man Strategien zur Programmentwicklung betrachtet, die solche Regeln verwenden, ist daher erst recht keine Effizienzverbesserung garantiert. Letztendlich ist der Benutzer solcher Werkzeuge selbst dafür verantwortlich, daß er tatsächlich effiziente Programme entwickelt. Es ist also nützlich, den Zeitaufwand von Programmen zu kennen, insbesondere, um im Programmentwicklungsprozeß Entwurfsentscheidungen treffen zu können. Keines der Werkzeuge unterstützt den Benutzer in der Aufgabe das Zeitverhalten eines Programms abzuschätzen. Der Werkzeugbenutzer nimmt daher (wenn überhaupt) nur eine oberflächliche Abschätzung seiner Zwischenresultate vor. Er wird im allgemeine höchstens die schlimmste und die günstigste Zeitkomplexität asymptotisch bestimmen. Eine weitaus wichtigere Rolle für die Praxis spielt der mittlere Zeitaufwand. Außerdem spielen die konstanten Summanden und Faktoren im Zeitaufwand eine nicht unerhebliche Rolle für die Effizienz des Programms.