Direkt zum Inhalt

Lexikon der Mathematik: worst case-Rechenzeit

die maximale Rechenzeit eines Algorithmus auf Eingaben der gleichen Länge, bei randomisierten Algorithmen (randomisierter Algorithmus) auch die maximale average case-Rechenzeit.

Da die Rechenzeit für spezifische Eingaben oft nur schwer berechenbar ist, gibt man sich mit der worst case-Rechenzeit zufrieden. Sie ist sehr aussagekräftig für Algorithmen, deren Rechenzeit zwar von der Länge, aber nicht stark vom Typ der Eingabe abhängt. Sie kann aber auch irreführend sein, wenn für einen großen Anteil der Eingaben die Rechenzeit viel kleiner als die worst case-Rechenzeit ist.

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

Artikel zum Thema

Partnervideos