Сотрудники :: Гасанов Эльяр Эльдарович :: Публикации Гасанова Э.Э.

О функциональной сложности двумерной задачи интервального поиска

Гасанов Э.Э., Кузнецова И.В.
Кафедра математической теории интеллектуальных систем, механико-математический факультет МГУ им М.В.Ломоносова

Скачать статью полностью в формате PDF (400 кб): ofunksl.pdf
Для просмотра Вам понадобится Adobe Acrobat Reader 4.x-5.x

 

Резюме:

Предлагается модификация алгоритма Бентли-Маурера, решающего двумерную задачу интервального поиска. Эта модификация позволяет снизить исходное логарифмическое среднее время поиска до константного при сохранении логарифмического времени поиска в худшем случае. При этом этот алгоритм зависит от параметра, при вариации которого объем памяти, необходимый алгоритму, изменяется от $O(k^3)$ до $O(k\log k)$, при этом среднее время поиска (без учета времени на перечисление ответа) изменяется от $O(1)$ до $O(\log k)$. В частности, для любого $\varepsilon>0$ при объеме памяти $O(k^{1+\varepsilon})$ достигается среднее время поиска $O(1)$. На основе этих результатов получены верхние оценки функциональной сложности двумерной задачи интервального поиска.


Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (грант 98-01-00130)

В печати

Наверх