Direkt zum Inhalt

Lexikon der Mathematik: average case-Rechenzeit

die durchschnittliche Rechenzeit eines Algorithmus auf Eingaben der gleichen Länge.

Zu unterscheiden ist, ob bei deterministischen Algorithmen eine Wahrscheinlichkeitsverteilung auf der Menge der Eingaben gegebener Länge vorgegeben ist und der Durchschnitt bezüglich dieser Verteilung gebildet wird, oder ob bei randomisierten Algorithmen für jede Eingabe die durchschnittliche Rechenzeit bezüglich der Zufallsentscheidungen des Algorithmus gebildet wird. Im zweiten Fall ist der worst case (worst case-Rechenzeit) der durchschnittlichen Rechenzeiten für Eingaben der gleichen Länge von Interesse.

Für viele praktische Probleme wie das Rucksackproblem oder das Traveling-Salesman-Problem läßt sich eine angemessene Wahrscheinlichkeitsverteilung auf der Menge der Eingaben gegebener Länge nicht angeben.

  • Die Autoren
- Prof. Dr. Guido Walz

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.