Lexikon der Mathematik: Güte eines Algorithmus
ein Bewertungsmaß für Algorithmen, die ein Approximationsproblem lösen.
Wenn ein Algorithmus auf Eingabe a eine Lösung mit Wert f(a) berechnet und fopt(a) der Wert einer optimalen Lösung ist, beträgt die Güte des Algorithmus für die Eingabe a bei Maximierungsproblemen fopt(a)/f(a) und bei Minimierungsproblemen f(a)/fopt(a). Die worst case Güte des Algorithmus ist für jede Eingabelänge das Supremum über die Güte des Algorithmus für die Eingaben der gegebenen Länge.
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.