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

  1. a b Marcin Sydow, Algorytmy i Struktury Danych [zarchiwizowane z adresu].
  2. Adrian Horzyk Podstawy informatyki - Złożoność i efektywność, home.agh.edu.pl [dostęp 2021-05-18].
  3. Złożoność obliczeń, eduinf.waw.pl [dostęp 2021-05-18].