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.
Schreiben Sie uns!