Direkt zum Inhalt

Lexikon der Mathematik: Komplexität im Mittel

bei der Untersuchung der Komplexität von Algorithmen und von Problemen die Betrachtung des durchschnittlichen Verhaltens, entweder bezogen auf Wahrscheinlichkeitsverteilungen über den Mengen von Eingaben gleicher Länge, oder in randomisierten Algorithmen (randomisierter Algorithmus), bezogen auf die verwendeten Zufallsbits.

Das wichtigste Maß für die Komplexität im Mittel ist die average case-Rechenzeit.

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