Rechenaufwand

Rechenaufwand bezeichnet in der Informatik den Ressourcenbedarf, der bei der Ausführung eines Algorithmus oder Programms entsteht. Er umfasst typischerweise den zeitlichen Aufwand (Laufzeit) sowie den speicherbezogenen Aufwand (Speicherbedarf).

Der zeitliche Rechenaufwand wird oft durch die Anzahl der Schritte oder die verstrichene Zeit beschrieben. In der Theorie wird er mithilfe der Komplexitätstheorie mit Grobabschätzungen wie der Big-O-Notation klassifiziert, oft im Worst-case, seltener im Best- oder Average-Case. Die asymptotische Analyse betrachtet, wie sich der Aufwand mit der Eingabegröße n verhält.

Der speicherbezogene Rechenaufwand beschreibt den benötigten Speicherplatz, inklusive zwischenspeicherter Werte, Stacks und Heaps. Auch hier werden meist Grenzwerte in der Form von Speicherkomplexität angegeben.

Die Bewertung des Rechenaufwands erfolgt sowohl theoretisch als auch empirisch. Theoretische Analyse liefert allgemeine Einschätzungen unabhängig von Implementierung und Hardware; empirische Messungen berücksichtigen konkrete Sprache, Compiler, Optimierungen und Hardware. Faktoren wie Parallelität, Cacheverhalten und Datenzugriffsmuster beeinflussen die tatsächliche Leistung.

Rechenaufwand ist ein zentrales Kriterium bei der Algorithmus- und Softwareentwicklung, beeinflusst Skalierbarkeit und Ressourcenbedarf. Ziel der Optimierung ist oft eine Verringerung des zeitlichen oder speicherlichen Aufwands, ggf. mit Kompromissen zwischen beiden Größen.