Direkt zum Inhalt

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.

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