Ocena brak

Czym różni się analiza złożoności algorytmu w średnim i w najgorszym przypadku?

Autor /Barnim7777 Dodano /29.12.2011

W analizie najgorszego przypadku badamy jaka będzie złożoność algorytmu w przypadku wystąpienia najniekorzystniejszych danych (np.: iteracyjny przegląd n –elementowej macierzy w poszukiwaniu elementu, którego na niej nie ma). Badanie takie daje nam pewną wiedzę o zachowaniu się algorytmu w takim przypadku.

W analizie średniego przypadku staramy się przewidzieć jakie rozwiązanie będzie pojawiało się najczęściej i właśnie dla niego staramy się obliczyć poziom złożoności algorytmicznej. W obliczeniach średniego przypadku istotną rolę odgrywają założenia o rozkładzie prawdopodobieństwa w zbiorze dopuszczalnych danych wejściowych.

Jeżeli mamy pewność, że szanse wystąpienia najgorszego wypadku są znikome, a dany algorytm ma zadowalającą złożoność średniego przypadku można zastanowić się nad jego zastosowaniem w danym programie.

Do góry