Direkt zum Inhalt

Lexikon der Mathematik: average case-Analyse

Analyse des erwarteten Verhaltens von Algorithmen, insbesondere der average case-Rechenzeit.

Bei deterministischen Algorithmen und zufälligen Eingaben und bei randomisierten Algorithmen ist die Rechenzeit eine Zufallsvariable, mit deren Analyse sich die average case-Analyse befaßt.

Neben dem Erwartungswert sind die Varianz und höhere Momente ebenso von Interesse wie obere Schranken, die mit sehr nahe bei 1 liegender Wahrscheinlichkeit unterschritten werden.

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