Algorytmy i struktury danych · Senior · Pytanie 50 z 75
Które stwierdzenie o przypadku średnim i najgorszym operacji tablicy haszującej jest poprawne?
- ✓Poprawna odpowiedź: Średnie O(1) zakłada dobry hasz; najgorszy przypadek to wciąż O(n)
- 2Zarówno średni, jak i najgorszy przypadek to O(1) w nowoczesnych silnikach
- 3Oba to O(log n), bo kubełki są drzewami
Wyjaśnienie
Oczekiwane O(1) opiera się na równomiernym rozkładzie kluczy. Niektóre implementacje (HashMap w Javie 8) zamieniają długie łańcuchy w drzewa, ograniczając najgorszy przypadek do O(log n), ale ogólnie tablica haszująca obiecuje tylko szybkość średnią.