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.
Copyright Springer Verlag GmbH Deutschland 2017
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.