Hash table - złożoność czasowa - Access i Search

Cześć,

szybkie pytanie,

zgodnie z tą tabelą:

(

złożoność czasowa jeśli chodzi o operację Search w przypadku Hash table wynosi O(1). Domniemam, że search to znaczy znaleźć klucz dla danej wartości i nie rozumiem dlaczego jest O(1), anie O(n) tak jak np. w przypadku zwykłej tablicy. Albo może operacja Search oznacza jednak coś innego?

Druga sprawa, w przypadku Hash Table, access oznaczone jest jako N/A. W tym przypadku też nie pojmuje, access rozumiem jako dostęp do pojedynczego elementu, który w przypadku zwykłej tablicy wynosi O(1) co jest dla mnie jasne (dostajemy się po indeksie), w przypadku hash table też moja intuicja podpowiada mi O(1), ponieważ dostajemy się po kluczu do elementu.

Byłbym super wdzięczny za klaryfikację.

1. Chodzi o znalezienie elementu o danej wartości, zakładam, że tutaj mamy doczynienia z tablicą i zbiorem haszującym a nie tablicą haszującą. Wtedy ma to sens, że znalezienie elementu w takich strukturach ma takie czasy jak podano.
2. Nie wiem dlaczego podano "N/A" ale zakładam, że z tego powodu, że to może zależeć od implementacji. Nie ma tam przypadkiem gdzieś przypisów?

Nie ma przypisów, podałem w poprzednim poście linka, ale coś mi go zjadło, więc jeszcze raz: http://bigocheatsheet.com

Zapoznaj się z https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/tutorial/. Dlaczego tablica ma Search O(n)? Ponieważ w najgorszym przypadku musisz przejrzeć wszystkie elementy żeby odpowiedzieć czy dany element jest w tablicy. W HashTable indeks elementu zależy od niego samego.

Szkolny przykład*: masz trzy rodzaje długopisów: czarny, czerwony, niebieski. Masz trzy pudełka, do pierwszy wkładasz tylko czarne, do drugiego tylko czerwone, do trzeciego tylko niebieskie. Ile pudełek musisz sprawdzić żeby wiedzieć czy masz długopis czerwony? Tylko jedną: otwierasz pudełko z czerwonymi długopisami. Nie musisz sprawdzać pudełek "czarnych" oraz "niebieskich" bo tam nie ma czerwonych. Jaka to jest złożoność? O(1) - odpowiedz na pytanie: czy mam czerwony długopis nie zależy od ilości pudełek. Gdybym kolorów było 20+ i tak byś musiał sprawdzić tylko jedno pudełko.

• Tak wiem, to co podałem to bardziej przykład MultiMapy.

W tym, że access jest N/A, chodzi zapewne o dostęp do elementu o jakimś indeksie, a hash table nie ma jakiegoś określonego porządku.

@lubie_programowac:

Czyli w przypadku search dla array szukamy wartości, a nie indeksu, a w przypadku hash table szukamy klucza, a nie wartości? Jeśli chcemy sprawdzić czy element o indeksie i istnieje w tablicy, to chyba nie musimy wszystkich przeglądać? Jeśli szukamy wartości to wtedy musimy przeglądać po kolei, więc O(n). W przypadku HashTable tak samo, chcemy sprawdzić czy klucz istnieje w hash table -> O(1), chcemy sprawdzić czy wartość istnieje w hash table -> nie powinno być również O(n)?

Nie powinno byc O(n), chyba, że nie Wiesz co Masz w hash table. Jeśli Wiesz, że kluczami są kolejne liczby naturalne, a wartościami kolejne liczby pierwsze, to Masz dostęp w czasie stałym do dowolnej liczby pierwszej (bo Wiesz, że, np., 11 jest wartościa dla klucza 4 ) .