Модель ячейки-зонда
-
Обзор модели клеточного зонда
- Модель клеточного зонда является модификацией машины с произвольным доступом, где операции с памятью бесплатны, кроме доступа к памяти.
- Используется для доказательства нижних границ сложности задач, связанных со структурой данных.
-
Фазы задач и сложность структуры данных
- Задачи включают две фазы: предварительную обработку и запрос.
- Сложность структуры данных определяется количеством обращений к ячейкам памяти во время предварительной обработки и запроса.
-
История и заметные результаты
- Эндрю Яо использовал модель для определения минимального количества зондирований для поиска данных в таблицах.
- Фредман и Сакс ввели обозначение CPROBE(b) и исследовали нижние границы для задач с динамическими структурами данных.
- Михай Петрашку улучшил результаты Фредмана и Сакса, показав, что задача о динамических частичных суммах требует Ω(log n) времени в худшем случае.
- Чакрабарти и Регев использовали модель для доказательства нижних границ времени запроса в задаче поиска ближайшего соседа на кубе Хэмминга.
-
Сравнение с машинами произвольного доступа
- Модель клеточного зонда ограничивает диапазон значений, которые могут храниться в ячейке, что отличает её от идеализированной машины произвольного доступа.
- Некоторые методы для определения нижних границ зонда ячейки могут быть перенесены в идеализированную оперативную память.