Algorytmy i struktury danych · Senior · Pytanie 61 z 75
Jakie jest dolne ograniczenie szukania elementu w nieposortowanej tablicy i dlaczego?
- 1Ω(log n): sprytnym próbkowaniem można je podzielić na pół
- 2Ω(1): haszowanie od razu go znajduje
- ✓Poprawna odpowiedź: Ω(n): cel może być na dowolnej niesprawdzonej pozycji
Wyjaśnienie
Argument przeciwnika: jeśli algorytm pominie pozycję, cel mógł być właśnie tam. Haszowanie pomaga dopiero po przygotowaniu w O(n), które buduje tablicę.