Złożoność pesymistyczna
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: [1].
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[1].
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[2][3].
Zobacz też
Przypisy
- ↑ a b Marcin Sydow , Algorytmy i Struktury Danych [zarchiwizowane z adresu] .
- ↑ Adrian Horzyk Podstawy informatyki - Złożoność i efektywność, home.agh.edu.pl [dostęp 2021-05-18] .
- ↑ Złożoność obliczeń, eduinf.waw.pl [dostęp 2021-05-18] .