Laufzeitkomplexität

Laufzeitkomplexität

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 Laufzeit und meint damit, in Anlehnung an eine Asymptote, das Zeitverhalten des Algorithmus für eine potenziell unendlich große Eingabemenge. Es interessiert also nicht der Zeitaufwand eines konkreten Programms auf einem bestimmten Computer, sondern viel mehr, wie der Zeitbedarf wächst, wenn mehr Daten zu verarbeiten sind, also z. B. ob sich der Aufwand für die doppelte Datenmenge verdoppelt oder quadriert (Skalierbarkeit). Die Laufzeit wird daher in Abhängigkeit von der Länge n der Eingabe angegeben und für immer größer werdende n asymptotisch unter Verwendung der Landau-Notation (Groß-O-Notation) abgeschätzt. Eine genauere Laufzeitabschätzung von Rekursionsgleichungen bietet auch das Mastertheorem oder die Substitutionsmethode.

Bezieht man den Begriff der Zeitkomplexität auf einen konkreten Algorithmus, so ist damit die Anzahl der Schritte gemeint, die der Algorithmus für die Bearbeitung einer Eingabe mit bestimmter Länge n benötigt (im besten, schlechtesten oder durchschnittlichen Fall, siehe unten). In der Komplexitätstheorie ist der eigentliche Gegenstand der Betrachtung aber die Komplexität von Problemen. Die Komplexität von Algorithmen ist nur insofern interessant, als man daraus Aussagen über das behandelte Problem schließen kann. In der Praxis ist diese aber häufig interessant, vor allem um für einen konkreten Kontext einen geeigneten Algorithmus auszuwählen: So ist Bubblesort zwar für große Datenmengen ein recht langsames Verfahren, eignet sich aber aufgrund des geringen Overheads gut für kleine Datenmengen (insbesondere für n ≤ 8).

Die Zeitkomplexität wird immer in Bezug auf ein Maschinenmodell angegeben. In der Regel ist das Bezugsmodell die Turingmaschine, alternativ kann die Zeitkomplexität aber auch in Bezug auf eine Registermaschine angegeben werden, die in ihrem Verhalten mehr den tatsächlich existierenden Computern ähnelt. Für parallele Algorithmen kann ein paralleles Maschinenmodell wie die PRAM verwendet werden. Zudem wird zwischen der Komplexität für deterministische und nichtdeterministische Maschinen unterschieden.

In der Komplexitätstheorie ist die Zeitkomplexität neben der Platzkomplexität der am häufigsten untersuchte Aspekt von Algorithmen und Problemen. Die Zeitkomplexität aller Algorithmen, die ein Problem lösen, liegt beispielsweise einer Reihe bedeutsamer Komplexitätsklassen zu Grunde.

Inhaltsverzeichnis

Varianten

Man unterscheidet die folgenden Varianten zur Laufzeitabschätzung:

  • Die worst-case-Laufzeit (engl. schlechtester Fall) gibt an, wie lange der Algorithmus maximal braucht. Für viele Algorithmen gibt es nur wenige Eingaben, die diese worst-case-Laufzeit erreichen, weshalb sie nicht unbedingt eine realistische Abschätzung ist. Handelt es sich aber um Echtzeitsysteme, so muss die worst-case-Laufzeit natürlich berücksichtigt werden.
  • Die average-case-Laufzeit (engl. durchschnittlicher Fall) gibt die erwartete Laufzeit bei einer gegebenen Verteilung der Eingaben an. Da allerdings die Verteilung der Eingaben bei Programmen nicht immer bekannt ist, ist die Berechnung der average-case-Laufzeit in diesen Fällen nur unter einschränkenden Annahmen möglich. Siehe auch: Amortisierte Laufzeitanalyse
  • Die best-case-Laufzeit (engl. bester Fall) gibt an, wie lange der Algorithmus in jedem Fall braucht, also selbst für die Eingaben, auf denen er ideal arbeitet. Diese untere Schranke zur Lösung des Problems wird nur selten angegeben, da sie nur für wenige Fälle zutrifft und die best-case-Laufzeit in der für die schlechteren Fälle enthalten ist.

Beispiel

In einer Liste werden zwanzig Namen gespeichert. Es soll nun ein vorhandener Name eingegeben und verglichen werden. Die Liste wird beginnend mit dem ersten Eintrag durchsucht bis der Name gefunden ist.

  • best case: Der gesuchte Name ist der erste in der Liste, die Suchzeit ist 1.
  • worst case: Der gesuchte Name ist der letzte in der Liste, Die Suchzeit ist 20. Diese Suchzeit würde sich auch einstellen, wenn der Name nicht in der Liste wäre.
  • average case: Ist der Name definitiv in der Liste, beträgt der average case 10.

Spricht man einfach von Zeitkomplexität, so ist meistens die Abschätzung für den worst case gemeint.

Für eine realistische Abschätzung der Laufzeit eignet sich bei komplexen Algorithmen die amortisierte Analyse, die die durchschnittlichen Kosten des Algorithmus für alle möglichen Eingaben betrachtet, statt nur für den besten/schlechtesten/gleichverteilten Fall. Dabei ist entscheidend, wie wahrscheinlich es ist, dass ein bestimmter Fall eintritt. Diese Art der Untersuchung eignet sich besonders, wenn man den Aufwand einer Teiloperation eines größeren Algorithmus betrachtet: Beim Sortieren mittels eines Fibonacci-Heaps beispielsweise ist die Operation des Einsortierens eines neuen Eintrags zwar im schlechtesten Fall recht aufwändig, aber diese kommen nur einmal beim Durchlauf des Gesamtalgorithmus vor, in allen folgenden Schritten ist der Heap bereits „fast sortiert“, und der einzelne Schritt ist billig. Das Problem an der amortisierten Analyse ist, dass sie nicht einfach durchzuführen ist, da man zunächst eine Funktion entwickeln muss, die das Verhalten der Datenstruktur möglichst genau modelliert und damit angibt, wie wahrscheinlich die einzelnen Fälle sind.

In der Informationstheorie wird die Zeitkomplexität verwendet, um die Algorithmische Tiefe einer Datenmenge zu bestimmen.

Siehe auch

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

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

  • Toom-Cook-Algorithmus — Der Toom Cook Algorithmus ist ein effizienter Algorithmus zur Multiplikation zweier ganzer Zahlen, der nach dem Prinzip Teile und herrsche arbeitet. Er wurde zuerst von Andrei Toom beschrieben, später durch Cook verbessert und in dessen… …   Deutsch Wikipedia

  • Karatsuba-Algorithmus — Der Karatsuba Algorithmus (1960) ist ein Algorithmus zur Multiplikation zweier ganzer Zahlen. Mit einer Laufzeitkomplexität von ist er deutlich schneller als der naive Algorithmus nach der Schulmethode. Dieser (und auch dessen implizite… …   Deutsch Wikipedia

  • Suchbaum-Komplexität — Dieser Artikel wurde aufgrund von inhaltlichen Mängeln auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf… …   Deutsch Wikipedia

  • AKS-Methode — Der AKS Primzahltest (auch bekannt unter dem Namen Agrawal Kayal Saxena Primzahltest) ist ein deterministischer Algorithmus, der für eine Zahl in polynomieller Laufzeit feststellt, ob sie prim ist oder nicht. Er wurde von den drei indischen… …   Deutsch Wikipedia

  • Agrawal-Kayal-Saxena-Primzahltest — Der AKS Primzahltest (auch bekannt unter dem Namen Agrawal Kayal Saxena Primzahltest) ist ein deterministischer Algorithmus, der für eine Zahl in polynomieller Laufzeit feststellt, ob sie prim ist oder nicht. Er wurde von den drei indischen… …   Deutsch Wikipedia

  • Bellman-Algorithmus — Der Algorithmus von Bellman konstruiert aus einer gegebenen Schlüsselliste und einer korrespondierenden Suchwahrscheinlichkeit einen optimalen binären Suchbaum. Der Algorithmus basiert auf dem von Richard Bellman 1957 gefundenen Satz über… …   Deutsch Wikipedia

  • Kontextfreie Grammatik — In der Theorie der formalen Sprachen ist eine kontextfreie Grammatik eine Grammatik, die nur solche Ersetzungsregeln enthält, bei denen immer genau ein Nichtterminal auf eine beliebig lange Folge von Nichtterminalen und Terminale abgeleitet wird …   Deutsch Wikipedia

  • Kontextfreie Grammatiken — Die kontextfreien Grammatiken sind eine Klasse formaler Grammatiken und sind identisch mit den Typ 2 Grammatiken der Chomsky Hierarchie. Inhaltsverzeichnis 1 Definition 2 Normalformen 3 Von G erzeugte Sprache 4 Eigenschaften …   Deutsch Wikipedia

  • Shakersort — Der Begriff Shakersort bezeichnet einen stabilen Sortieralgorithmus, der eine Menge von linear angeordneten Elementen (z. B. Zahlen) der Größe nach sortiert. Weitere Namen für diesen Algorithmus sind Cocktailsort, Ripplesort, Shearsort oder… …   Deutsch Wikipedia

  • Smith-Waterman-Algorithmus — Der Smith Waterman Algorithmus ist ein Algorithmus, der den optimalen lokalen Alignment Score (similarity score) bzw. das optimale lokale Alignment zwischen zwei Sequenzen berechnet. Ein Sequenzalignment ist eine Folge von Edit Operationen (wie z …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”