Pr-1st-1.1-m10-Slajd54

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Algorytm detekcji zakończenia statycznego: Złożoność

Algorytm detekcji zakończenia statycznego: Złożoność


Efektywność, atakże złożoność czasowa i komunikacyjna, algorytmu zależy od implementacji cykli detekcyjnych itopologii przetwarzania monitorującego.

W celu wyznaczenia złożoności czasowej zauważmy, że po wystąpieniu zakończenia statycznego, dla jego stwierdzenia potrzebne są w najgorszym przypadku dwa pełne cykle detekcyjne oraz musi być dokończony cykl bieżący.

W każdym cyklu przesyłanych jest n wiadomości typu QUERY i n wiadomości typu REPLY przenoszących jednobitową zmienną. Tak więc zaniedbując wiadomości potwierdzeń (których liczba jest równa liczbie wiadomości aplikacyjnych), otrzymujemy liczbę wiadomości kontrolnych wystarczających do stwierdzenia zakończenia, równą: .

Przyjmijmy teraz, że struktura topologiczna przetwarzania detekcyjnego jest grafem w pełni połączonym. Pomijając ponownie wiadomości potwierdzeń, łatwo już zauważyć, że złożoność czasowa algorytmu wynosi . Oczywiście przy innych topologiach złożoność ta zmienia się odpowiednio. Przykładowo, w przypadku pierścienia złożoność czasowa wyniesie .


<< Poprzedni slajd | Spis treści | Następny slajd >>