Pr-1st-1.1-m05-Slajd50: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
Nie podano opisu zmian |
||
| Linia 1: | Linia 1: | ||
==Złożoność czasowa algorytmu detekcji zakleszczenia w środowisku synchronicznym dla modelu k spośród r (1)== | ==Złożoność czasowa algorytmu detekcji zakleszczenia w środowisku synchronicznym dla modelu k spośród r (1)== | ||
[[Image: | [[Image:Pr-1st-1.1-m05-Slajd50.png|Złożoność czasowa algorytmu detekcji zakleszczenia w środowisku synchronicznym dla modelu k spośród r (1)]] | ||
Przeanalizujmy teraz złożoność czasową tego algorytmu, przyjmując, że graf niezorientowany odpowiadający grafowi zorientowanemu, scharakteryzowany jest przez średnicę grafu d i najdłuższą ścieżkę w grafie – l. W ostatnim z prezentowanych przykładów, ''d'' = 1 a ''l'' = 3. | Przeanalizujmy teraz złożoność czasową tego algorytmu, przyjmując, że graf niezorientowany odpowiadający grafowi zorientowanemu, scharakteryzowany jest przez średnicę grafu d i najdłuższą ścieżkę w grafie – l. W ostatnim z prezentowanych przykładów, ''d'' = 1 a ''l'' = 3. | ||
| Linia 8: | Linia 8: | ||
[[ | [[Pr-1st-1.1-m05-Slajd49 | << Poprzedni slajd]] | [[Pr-1st-1.1-m05-toc|Spis treści ]] | [[Pr-1st-1.1-m05-Slajd51 | Następny slajd >>]] | ||
Aktualna wersja na dzień 15:55, 7 wrz 2006
Złożoność czasowa algorytmu detekcji zakleszczenia w środowisku synchronicznym dla modelu k spośród r (1)
Przeanalizujmy teraz złożoność czasową tego algorytmu, przyjmując, że graf niezorientowany odpowiadający grafowi zorientowanemu, scharakteryzowany jest przez średnicę grafu d i najdłuższą ścieżkę w grafie – l. W ostatnim z prezentowanych przykładów, d = 1 a l = 3.
Ponieważ faza potwierdzania jest zagnieżdżona w fazie powiadamiania, to aby wyznaczyć złożoność całego algorytmu trzeba dodać do złożoności fazy potwierdzania złożoność powiadomienia inicjatora fazy potwierdzania (przekazania mu wiadomości typu NOTIFY), jak również złożoność odpowiadającą przesłaniu wiadomości typu DONE od inicjatora fazy potwierdzania do inicjatora detekcji.
