Hej,
Może ktoś z Was wie, jak się definiuje złożoność pesymistyczną dla algorytmów probabilistycznych?
Jako algorytm probabilistyczny rozumiem algorytm, który korzysta z generatora pseudolosowego. Wiadomo, że liczba kroków (lub zajętej pamięci) takiego algorytmu będzie zależna od 2. czynników:
- rozwiązywanego problemu
- konkretnej sekwencji z generatora
Złożoność pesymistyczną określa się zawsze dla "najgorszego przypadku". Tylko co tutaj jest najgorszym przypadkiem? Czy biorę tylko <najgorszy problem="problem"> i liczę średnią dla różnych sekwencji losowych generatora, czy biorę parę <najgorszy problem, najgorsza sekwencja>? Sensowniejsze wydaje sie to pierwsze, bo na podstawie drugiego moznaby wnioskowac, ze analiza najgorszego przypadku dla wiekszosci losowych algorytmow konczy sie zawsze jednym wnioskiem: algorytm nie dziala.
Jakoś nie mogę tego nigdzie w necie znaleźć, a pechowo jestem chory i wycieczka do biblioteki po jakąś poważną książkę na temat alg. probabilistycznych nie wchodzi w grę. W zwykłych książkach i wykładach do analizy algorytmów tego NIE MA :(