English version of this page
На главную страницу
Официальный сайт кафедры Математической теории интеллектуальных систем и лабораторий Проблем теоретической кибернетики и Математичеких проблем искусственного интеллекта механико-математического факультета МГУ им. М. В. Ломоносова
На первую страницу сайта Новости Кафедра Сотрудники Учеба Наука Исследования Журнал Культура Канал кафедры МаТИС в Телеграм

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

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

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

Скачать статью полностью в формате 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)

В печати

Наверх

   © 2001- г. Кафедра Математической теории интеллектуальных систем, лаборатория ПТК, лаборатория МПИИ Написать вебмастеру   
Последние новости - в телеграм-канале кафедры МаТИС: Канал кафедры МаТИС в Телеграм Rambler's Top100 Рейтинг@Mail.ru