Алгоритми та структури даних · Senior · Запитання 61 з 75
Яка нижня межа для пошуку елемента в невідсортованому масиві і чому?
- 1Ω(log n): хитрим зондуванням її можна поділити навпіл
- 2Ω(1): хешування знаходить її одразу
- ✓Правильна відповідь: Ω(n): ціль може бути в будь-якій неперевіреній позиції
Пояснення
Аргумент супротивника: якщо алгоритм пропускає позицію, ціль могла бути саме там. Хешування допомагає лише після підготовки за O(n), яка будує таблицю.