Analiza probabilistyczna algorytmów
W analizie algorytmów probabilistyczna analiza algorytmów jest podejściem do oszacowania złożoności obliczeniowej algorytmu lub problemu obliczeniowego. Wychodzi z założenia o probabilistycznym rozkładzie zbioru wszystkich możliwych danych wejściowych. To założenie jest następnie wykorzystywane do zaprojektowania wydajnego algorytmu lub do wyprowadzenia złożoności znanego algorytmu. To podejście nie jest takie samo, jak w przypadku algorytmów probabilistycznych , ale można je łączyć.
W przypadku algorytmów nieprobabilistycznych, a dokładniej deterministycznych , najbardziej powszechnymi typami oszacowań złożoności są złożoność średniego przypadku i złożoność prawie zawsze. Aby uzyskać złożoność średniego przypadku, przy danym rozkładzie danych wejściowych, oceniany jest oczekiwany czas algorytmu, podczas gdy dla oszacowania złożoności prawie zawsze ocenia się, że algorytm dopuszcza dane oszacowanie złożoności, które prawie na pewno jest spełnione .
W analizie probabilistycznej algorytmów probabilistycznych (randomizowanych) oprócz rozkładów wejściowych brane są pod uwagę również rozkłady lub średnia wszystkich możliwych wyborów w krokach losowych.