Laufzeit (Informatik)


Laufzeit (Informatik)

Der Begriff Laufzeit (engl. runtime) beschreibt in der Informatik im Wesentlichen die Zeitspanne, während der ein Programm von einem Rechner ausgeführt wird, und zwar sowohl in Bezug auf die Zeitdauer, die zur Bewältigung einer Aufgabe benötigt wird, als auch zur Beschreibung, dass ein Programm zu einem bestimmten Zeitpunkt gerade ausgeführt wird.

Laufzeit als Dauer der Ausführung

Die Länge der Zeitspanne, die zur Lösung einer Aufgabe benötigt wird, lässt sich häufig nur durch Ausprobieren bestimmen. Jeder Befehl eines Programms in einer höheren Programmiersprache wird vom Compiler in eine vorher nicht zwingend bekannte Anzahl von Maschinenbefehlen übersetzt. Die Ausführung eines Befehls kann, je nach Hardware, weitere Verzögerungen ergeben – wenn z. B. Daten zwischen Hauptspeicher und Cache ausgetauscht oder von der Festplatte in den Speicher eingelagert werden müssen (Paging). Weitere Abhängigkeiten ergeben sich von Betriebssystem, CPU-Taktrate, Größe des Hauptspeichers, Übertragungsrate des internen Bus-Systems usw. Auch möchte man etwa abschätzen, wie sich das untersuchte Programm unter Variation der Größen der Eingangsvariablen, der Instanzen, verhält.

In der Informatik gibt man daher Laufzeiten von Algorithmen nicht in Zeiteinheiten an. Stattdessen sucht man eine obere Schranke an die Anzahl der einfachen Operationen, auch Elementarschritte, in der Größe der Instanz und verwendet die Landau-Notation.

Einige Beispiele anhand eines Programms, das n Zahlen sortiert:

  • \mathcal{O} (n)“ beschreibt ein lineares Wachstum. Solch ein Programm macht pro eingegebener Zahl nur eine konstante Anzahl von Rechenschritten. Werden beispielsweise doppelt so viele Zahlen eingegeben verdoppelt sich auch die Ausführungsdauer.
  • \mathcal{O} (n²)“ bedeutet quadratisches Wachstum. Das Sortierprogramm macht pro eingegebener Zahl eine konstante Anzahl von Durchläufen durch die ganze Liste. Bei doppelter Größe der Eingabedaten kommt es hier also etwa zu einer Vervierfachung der Ausführungsdauer.
  • \mathcal{O} (2n)“ würde schließlich exponentielles Wachstum bedeuten. Im Beispiel des Sortierprogramms würde sich mit jeder weiteren Zahl die Laufzeit (ungefähr) verdoppeln, was bereits bei verhältnismäßig kleinen Eingabegrößen zu extrem langen Laufzeiten führt. Solch einen Zeitverbrauch erreicht ein Sortierprogramm beispielsweise, indem es alle möglichen Reihenfolgen der Zahlen daraufhin testet, ob sie sortiert sind.

Verfahren mit exponentieller Laufzeit versucht man daher nach Möglichkeit zu vermeiden – ob das überhaupt geht, ist eine der Fragen, die man sich in der Theoretischen Informatik stellt (vgl. dazu Komplexitätstheorie und NP-vollständig). Angestrebt werden Verfahren mit polynomieller, also salopp gesagt „n hoch irgendwas“, oder noch besser logarithmischer Laufzeit \mathcal{O}(log n). Heute gebräuchliche Sortierverfahren erreichen meist eine worst case Laufzeit von \mathcal{O}(n·log n) oder \mathcal{O}(n2). Man beachte dabei, dass ein Programm im Grunde dreigeteilt ist – Eingabe, Verarbeitung, Ausgabe – und dass sich nur der mittlere Teil in dieser Hinsicht optimieren lässt (Ein- und Ausgabe haben in der Regel lineares Zeitverhalten − es muss ja jeder einzelne Wert eingelesen/ausgegeben werden).

Laufzeit als Teil des Entwicklungsprozesses

Laufzeit (runtime) bezeichnet die Phase der Ausführung eines Programms, also seine tägliche Verwendung durch den Benutzer, meist ohne Zugriffsmöglichkeiten für Entwickler. Insofern im Zuge der Ausführung bestimmte Eigenheiten – besonders Fehler – zu Rückmeldungen an die Entwickler führen können und damit Impulse zu Änderungen geben, können Erprobung und Verwendung eines Programms als Teil des Entwicklungsprozesses angesehen werden.

Weitere Phasen sind z. B. die Übersetzungszeit (compiletime) den Zeitpunkt der automatischen Übersetzung des Quelltextes oder die linktime den Zeitpunkt des Zusammenführens der Programmkomponenten zu einer ausführbaren Einheit. Das eigentliche Programmieren und Modellieren wird mitunter als precompiletime bezeichnet.

Siehe auch


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Laufzeit — bezeichnet: Laufzeit (Zeitschrift), eine monatlich erscheinende Laufsport Zeitschrift die Zeitspanne, während der etwas geschieht: in der Wirtschaft die Zeit zwischen Investition und erwarteter Ausschüttung von Kapital (z. B. bei… …   Deutsch Wikipedia

  • Informatik — ist die „Wissenschaft von der systematischen Verarbeitung von Informationen, besonders der automatischen Verarbeitung mit Hilfe von Digitalrechnern“ [1]. Historisch hat sich die Informatik einerseits aus der Mathematik entwickelt, andererseits… …   Deutsch Wikipedia

  • Keller (Informatik) — Vereinfachte Darstellung eines Stacks mit den Funktionen Push (drauflegen) und Pop (runternehmen) In der Informatik bezeichnet ein Stapelspeicher oder Kellerspeicher (kurz Stapel oder Keller, häufig auch mit dem englischen Wort Stack bezeichnet)… …   Deutsch Wikipedia

  • Introspektion (Informatik) — In der Programmierung bedeutet Reflexion (engl. reflection) bzw. Introspektion, dass ein Programm seine eigene Struktur kennt und diese, wenn nötig, modifizieren kann. Auf unterster Ebene kann Maschinencode im RAM, der von einem Mikroprozessor… …   Deutsch Wikipedia

  • Internationalisierung (Informatik) — Internationalisierung bedeutet in der Informatik bzw. in der Softwareentwicklung, ein Programm so zu gestalten, dass es leicht (ohne den Quellcode ändern zu müssen) an andere Sprachen und Kulturen angepasst werden kann. Internationalisierung… …   Deutsch Wikipedia

  • Effizienz (Informatik) — Die Effizienz eines Algorithmus ist seine Sparsamkeit bezüglich der Ressourcen, Zeit und Speicherplatz, die er zur Lösung eines festgelegten Problems beansprucht. Mit steigender Effizienz sinkt die Komplexität eines Algorithmus. Jedoch sind… …   Deutsch Wikipedia

  • Asymptotische Laufzeit — Unter der Zeitkomplexität eines Problems versteht man die Anzahl der Rechenschritte, die ein optimaler Algorithmus zur Lösung dieses Problems benötigt, in Abhängigkeit von der Länge der Eingabe. Man spricht hier auch von der asymptotischen… …   Deutsch Wikipedia

  • Worst-Case-Laufzeit — Unter der Zeitkomplexität eines Problems versteht man die Anzahl der Rechenschritte, die ein optimaler Algorithmus zur Lösung dieses Problems benötigt, in Abhängigkeit von der Länge der Eingabe. Man spricht hier auch von der asymptotischen… …   Deutsch Wikipedia

  • Allokation (Informatik) — Unter Allokation versteht man in der Informatik die Reservierung von Hauptspeicher oder anderen Ressourcen zur eigenen Verwendung. Inhaltsverzeichnis 1 Hintergrund 2 Zeitpunkt der Allokation 3 Sprachliches 4 Einzelnac …   Deutsch Wikipedia

  • Profiling (Informatik) — Als Profiler werden Programmierwerkzeuge bezeichnet, die das Laufzeitverhalten von Software analysieren. Es gibt unterschiedliche Problembereiche in der Softwareentwicklung, die durch ineffiziente Programmierung ausgelöst werden. Ein Profiler… …   Deutsch Wikipedia