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.

Lesermeinung

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.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos