Złożoność pesymistyczna określa złożoność w „najgorszym” przypadku. Jeśli oznacza zbiór wszystkich możliwych danych wejściowych, jeden z elementów tego zbioru, a funkcję, która dla danego zwraca liczbę operacji, to złożoność pesymistyczna jest zdefiniowana jako: .
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
Przypisy
Kategoria:Teoria obliczeń