Es wird dabei auf der Grundlage der obigen Modellvorstellungen angenommen, daß alle Operationen gleich lange dauern, unabhängig von der speziellen Art der Operationen und unabhängig von den Operanden. Eine Abschätzung des gesamten Zeitaufwandes der Algorithmus-Ausführung (abhängig von der Problemgröße) ist möglich, wenn man den Zeitaufwand für die Durchführung einer Operation kennt.
Diese reine Abzählung der gleich gewichteten Operationen setzt aber eine identische Arbeitsmenge für jede Operation voraus. Auf Grund dieser Vereinfachung kann der theoretische Abarbeitungsaufwand nur für qualitative oder grobe quantitative Aussagen verwendet werden.
Direkte Algorithmen der linearen Algebra (Eliminationsalgorithmen) erfüllen beispielsweise diese Bedingung. Ganz anders ist die Situation bei iterativen Algorithmen, da hier nicht allein die Größe des Problems Einfluß auf die Anzahl der erforderlichen Operationen hat, sondern auch noch andere Parameter, wie Genauigkeitsschranken, Distanz des Startwerts der Iteration von der gesuchten Lösung, Eigenschaften der Gleitpunktarithmetik etc. (Mayes 297). Die Anzahl der Operationen, die für die Durchführung eines derartigen Algorithmus benötigt werden, ist daher nicht vorhersagbar. Eine Komplexitätsanalyse solcher Algorithmen ist allenfalls unter sehr einschränkenden Zusatzvoraussetzungen möglich.
Grundsätzlich kann man bei Algorithmen, bei denen der Arbeitsaufwand a priori nicht bekannt ist, keine allgemeinen theoretischen Aussagen darüber machen, welche Arbeitsmenge zur Problemlösung anfällt. In diesen Fällen kann man allenfalls die Komplexität eines Berechnungsschritts bestimmen. Wie oft jedoch so ein Schritt durchgeführt werden muß, damit die Ergebnisse den Anforderungen genügen, hängt von den Eigenschaften der konkreten Problemstellung ab.
Beispiel (Adaptive Verfahren der numerischen Integration) Ein adaptiver Algorithmus zur numerischen Integration ist folgendermaßen aufgebaut (vgl. Kapitel 12): Die Werte des Integranden an bestimmten Stellen des Integrationsbereichs sind die Information, aus der ein Integralnäherungswert und eine Fehlerschätzung berechnet werden. Aus der laufenden Erfassung von Integralnäherungswerten und Fehlerschätzungen auf Teilbereichen wird anhand eines Gütekriteriums entschieden, auf welchen Teilbereichen weitere Unterteilung und Durchführung von Integrationsschritten notwendig ist. Der numerische Integrationsvorgang kann eventuell schon nach dem ersten Schritt beendet sein, sodaß überhaupt kein Teilbereich, sondern nur der gesamte Integrationsbereich betrachtet werden muß.
Der Arbeitsaufwand eines Integrationsschrittes auf einem festen Bereich läßt sich zwar genau bestimmen, aber die zur Erfüllung des Gütekriteriums benötigte Unterteilungstiefe und damit die Anzahl der Integrationsschritte hängt von den Eigenschaften des Integranden ab und läßt sich nicht von vornherein abschätzen.
Die bei einem adaptiven Verfahren zu leistende Arbeit kann also a priori
nicht festgestellt werden. In solchen Fällen ist es sinnvoll,
für Aufwandsbewertungen die Arbeit auf Teilbereichen anstelle der gesamten
Arbeit heranzuziehen. Die in Abschnitt 3.3.1 angesprochene
Verwendung von hinreichend kleinen zeitlichen Intervallen
läßt sich analog auf hinreichend kleine örtliche
Bereiche umsetzen.