Dair_Targ
@Dair_Targ

Структура данных

Подскажите структуру данных, для которой:
  • Время вставки: гарантированно O(1) (желательно со скоростью вставки в linked list)
  • Время доступа к произвольному элемету по его номеру в списке тоже гарантированно O(1) (желательно со скоростью доступа к элементу массива)

В структуре будут хранится указатели или целые числа. Время работы других операций не имеет значения.
  • Вопрос задан
  • 2979 просмотров
Пригласить эксперта
Ответы на вопрос 4
@MikhailEdoshin
По-моему, единственный вариант с ожидаемым O(1) — хэш-таблица. Если данные известны, можно подобрать perfect hash function и тогда O(1) будет гарантирован.
Ответ написан
kefiijrw
@kefiijrw
ээммм. боюсь опозориться на виду у всего района, но… динамический массив?
Ответ написан
Artemzr
@Artemzr
Хэш-таблица наверное самый подходящий вариант. Для устранения коллизии заменяйте каждый элемент списком либо делайте открытую адресацию.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы