Złożoność pesymistyczna

Złożoność pesymistyczna określa złożoność w „najgorszym” przypadku. Jeśli $D$ oznacza zbiór wszystkich możliwych danych wejściowych, $d$ jeden z elementów tego zbioru, a $f$ funkcję, która dla danego $d$ zwraca liczbę operacji, to złożoność pesymistyczna jest zdefiniowana jako: $\sup \{f(d):d\in D\}$.

Pesymistyczna złożoność czasowa, oznaczana W() (od ang. “worst”) to funkcja wyrażająca kres górny możliwej liczby operacji dominujących dla ustalonego rozmiaru danych (wariant pesymistyczny). Wyraża liczbę wykonanych operacji dominujących w najgorszym (pesymistycznym) przypadku.

W przypadku złożoności obliczeniowej algorytmu złożoność pesymistyczna O() jest ilością zasobów (np. czasu lub dodatkowej pamięci) potrzebnych do wykonania algorytmu przy założeniu najbardziej złośliwych lub najgorszych danych.

Zobacz też

• złożoność obliczeniowa
• złożoność oczekiwana