Witam.
Zacząłem ostatnio używać Dictionary do przechowywania różnych rzeczy w moim programie.
I chciałbym się dowiedzieć jaka jest złożoność obliczeniowa dla operacji pobierania jeżeli przechowywane są tam tylko stringi?
Wyczytałem, że operacja pobierz z reguły ma czas O(1) jedynie w sytuacji, gdy pod jednym hashem przechowywane jest kilka wartości mowa wtedy o kolizji.
Jednak jeżeli wiemy, że w słowniku mogą wystąpić kolizje to wtedy czas wynosi O(n) dla każdego przypadku czy tylko dla indeksu, który ma w sobie listę elementów?
Chodzi mi przede wszystkim jak to się ma w kontekście przede wszystkim Dictionary z c#.
0
0
kenik napisał(a):
Jednak jeżeli wiemy, że w słowniku mogą wystąpić kolizje to wtedy czas wynosi O(n) dla każdego przypadku czy tylko dla indeksu, który ma w sobie listę elementów?
Sprawdzałeś jak są rozwiązywane kolizje czy implicite założyłeś, że są to jakieś listy?
Pobieranie danych z Dictionary ma zamortyzowany czas stały, tzn. dla n wyszukań kluczy czas to O(n).
0
No jeśli założysz, że kolizje nie występują to chyba oczywiste jest, że czas znalezienia klucza jest stały. Nawet jeśli kolizje występują, ale wybrana jest sensowna funkcja haszująca, to ten czas jest stały zamortyzowany, bo tak mówi rachunek prawdopodobieństwa - kolizji będzie stosunkowo mało. Pesymistycznie to O(n), bo istnieją funkcje haszujące, które wszystkie klucze wrzucą do jednego worka.