Полная версия

Главная arrow Информатика arrow ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ. ТЕОРИЯ ХРАНЕНИЯ И ПОИСКА ИНФОРМАЦИИ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

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

Метод поиска, описанный в теореме 50, для двумерной задачи интервального поиска требует памяти порядка А:3, где к — объем библиотеки. Поэтому представляется актуальным разработка алгоритмов, имеющих меньшие затраты памяти, может быть за счет ухудшения показателей времени.

В данном разделе предлагается алгоритм решения двумерной задачи интервального поиска, зависящий от некоторого параметра. При вариации этого параметра получаются разные соотношения объема памяти и среднего времени поиска. Данный алгоритм является модификацией алгоритма Бентли-Маурера, изложенного в [116], но в отличие от исходного алгоритма предлагаемый алгоритм при сохранении порядка оценок объема памяти и времени в худшем случае имеет константные оценки времени в среднем.

Результаты данного раздела были анонсированы в [38, 160], и опубликованы в [45].

Формулировка результата.

Дадим описание типа задач поиска, который соответствует двумерной задаче интервального поиска.

Пусть Yint2 = [ 0,1)2 — множество записей и

— множество запросов. Пусть на множестве Xint2 задано вероятностное пространство (Xint2,<7, Р), где Р задается функцией плотности вероятности р(х).

Отношение поиска pint2 определено на Xint2 х Yint2 и задается следующим соотношением:

Тогда тип

назовем типом двумерного интервального поиска.

Определим базовое множество

Для удобства будем считать, что функция плотности вероятности р(х) = p(tzi,t;i,tt2,V2)i определяющая вероятностную меру Р вероятностного пространства над Xint2i задана на [О, I)2, но вне X{nt2 она принимает значение 0.

Обозначим

где Zi = (ui,Vi), i = 1,2.

Пусть 6, d, е, / € [ 0,1) и 6 < d, е < /, Ь ^ е. Обозначим

Пусть с — некоторая вещественная константа. Скажем, что функция плотности вероятности р(х) = p(ui,vi,ii2,иг) обладает свойством с-ограниченности, если для любых b,d,e,f € [0,1), таких что b < d, е < /, 6 ^ е выполняются условия

Теорема 52. Пусть I = (Xint2, V,Pint2) ~ двумерная задача интервального поиска, где V = к. Пусть Т — базовое множество, определяемое соотношениями (4.53)-(4.60). Пусть R(I) = = Ylytv P(0(y,p<nt2))- Тогда если для некоторой константы с функция плотности вероятности р(х), определяющая вероятностную меру Р, обладает свойством с-ограниченности, то для любого натурального М такого, что 1 ^ М ^ 2 In к, справедливо

причем для ИГ U*, на котором достигается верхняя оценка, для любого х G Xint2 выполняется

При вариации параметра М мы получаем серию оценок функциональной сложности задачи в различных точках. Так если М = 2, то при объеме памяти Q = 4А:2/3 мы имеем среднее время поиска (без времени перечисления ответа) Т = 26. Для любой константы е > > 0 мы можем выбрать параметр М = ]2/е[ так, что при объеме памяти Q = 0(к1+е) мы имеем среднее время Т = 16М — 6 = = 16]2/е[ — 6 = const. Ограничение сверху на параметр М, приведенное в теореме, объясняется тем, что функция Q(M) = Мк1+2^м имеет точку минимума М = 2п к, функция Q2(M) = Мк1+1^м имеет точку минимума М = In А:, функция Q$(M) — является

убывающей по М, причем (2з(1пА:) = ек. Поэтому после точки М = = 21nfc объем Q(M) данного метода заведомо будет возрастать при одновременном возрастании среднего времени поиска Т(М). Поэтому при минимальном по порядку для предлагаемого метода объеме Q = = 0(к log к) мы имеем среднее время Т = 0(logA:), что соответствует по порядку методу Уилларда [212] и Л юкера [182], но в силу сложности своих конструкций предлагаемый метод в данном случае является менее предпочтительным, чем метод Уилларда-Люкера.

Нижняя оценка следует из теоремы 4 (мощностная нижняя оценка).

Здесь будет приведено доказательство верхней оценки.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>