Оценки памяти константного в худшем случае алгоритма поиска.

В данном разделе рассматривается задача поиска идентичных объектов в ее геометрической интерпретации, которая звучит следующим образом. Дано конечное подмножество V = {у,... ,2д} точек из отрезка [0,1] вещественной прямой. Требуется построить условный алгоритм, который для произвольной точки х € [0,1) (эта точка называется запросом) позволяет найти номер точки из множества V, которая совпадает с х (если такая точка в V существует), при условии, что мы умеем выполнять следующие операции над веществешшши числами: арифметические операции (сложение, вычитание, умножение, деление, взятие целой части вещественного числа), операции сравнения и возможно некоторые другие простейшие операции. При этом допускается предобработка данных, которая может состоять в сортировке данных (множества V), а также в построении некоторых дополнительных структур.

В данном разделе детализируется алгоритм, описанный в предыдущем пункте, применительно к данной геометрической интерпретации, и показывается, что для почти всех задач поиска идентичных объектов (т. е. при вариации множества V) данный алгоритм позволяет при объеме памяти порядка к2 решать задачу в худшем случае за константное число элементарных операций, т. е. операций, которые обычно используются в компьютерах. Здесь под объемом памяти понимается количество ячеек для хранения вещественных чисел, куда можно поместить данные и дополнительные структуры, а худший случай берется по множеству всех возможных значений запроса, т. е. по множеству [0,1). Здесь для упрощения дальнейшего изложения мы выбросили точку 1 из множества запросов.

Результаты данного раздела опубликованы в [40, 162].

Опишем предлагаемый алгоритм. Пусть нам дано множество V = = {уъ2/2> • • •, Ук}, в котором производится поиск. Это множество будем называть библиотекой. Выполним следующую предобработку. Упорядочим точки из V в порядке возрастания и, чтобы не усложнять обозначения, далее считаем, что у < у2 < .. • < Ук- Находим число dy = min (yi — Пусть m = ]1 /dy[ наименьшее целое,

2^.i^k

не меньшее, чем 1 /dy. Выделим место под массив целых длины т, и элементы этого массива будем обозначать п* (г = 0,1,2,..., га — 1). Разделим отрезок [0,1] на т равных частей:

В каждую часть может попасть не более одной точки из множества V Теперь заполним массив щ следующим образом:

где г = 0,1,2,... ,m - 1.

После того как сделана данная предобработка, поиск будем осуществлять следующим образом. Пусть нам дан запрос х € [0,1). Вычислим j = [хтп] — целая часть числа хт. Понятно, что х € € Aj. Если rij равно — 1, то в библиотеке V нет числа равного х. В противном случае сравниваем уп. с х и если они равны, то номер rij является ответом задачи, иначе ответ пуст. Тем самым в худшем случае мы выполняем одну операцию умножения, одну операцию взятия целой части, одну операцию сравнения целых чисел, одну операцию сравнения вещественных чисел и две операции извлечения элемента массива, всего 6 элементарных операций. Объем памяти, необходимый данному алгоритму, равен сумме объемов массивов целых чисел длины т и вещественных чисел длины к. Ниже приводятся результаты, оценивающие величину т.

Пусть к — натуральное число, большее 1 и ?1,^2 »•••»?* — независимые равномерно распределенные на отрезке [0,1] случайные величины. Пусть

Эта величина исследовалась, например, в [47, 139].

Пусть г — вещественное число и f(k,r) = Р(d(?i,• • • ,?*) ^ г) — вероятность того, что минимальное расстояние между парами различных точек & (г = 1,2,..., п) не меньше г.

Если считать, что библиотеки V получаются случайным независимым бросанием к точек на отрезок [0,1], где вероятность попадания в любую пару отрезков одинаковой длины одинакова, то /(&, г) равна доле множества /^-элементных библиотек, у которых минимальное расстояние между любыми двумя точками не меньше чем г, по отношению к множеству всех библиотек мощности к.

Справедлива следующая теорема.

Теорема 15.

Доказательство. Пусть I — вещественное число из отрезка [0,1], г — вещественное число, к — натуральное число, большее 1, п — такое натуральное число, что 1 ^ п ^ к. Пусть Х, Хг,..., х* — независимые равномерно распределенные на отрезке [0,1] случайные величины. Обозначим через В(п, г, I) событие, что точки xi,Х2,...,хп попадают в отрезок [0,/], и минимальное расстояние между парами различных точек х, (* = 1,2,...,п), не меньше г. Обозначим через /(п,г,/) = = Р(Б(п,г,/)). Понятно, что если г < 0, то /(п,г,/) = /п, а при г > > 1/{п — 1), /(п,г, /) = 0. Поэтому мы будем рассматривать только случай, когда 0 ^ г ^ 1/(п — 1).

Лемма 13. Если 0 ^ г ^ 1/(п - 1), то /(п,г,/) = (/ — (п - 1) • г)п.

Доказательство будем вести индукцией по п.

Базис индукции, п = 2.

Поскольку возможны два равновероятных события: случай когда xi < Х2, и когда Х2 < Xi, то достаточно рассмотреть первую ситуацию и удвоить полученный результат. Поскольку в этом случае х может меняться от 0 до / г, а Х2 — от Xi + г до /, то

Индуктивный переход. Пусть утверждение леммы справедливо для любого натурального q < п и любого вещественного I G [0,1].

Через Л{ обозначим событие, что случайная величина х,-, максимальна среди величин х,..., хп, здесь г = 1,..., п. Понятно, что если iyj ? {1,... ,п} и г ф jj то Ау П Aj = 0, кроме того P(j4j) = 1/п, для любого г € {1,... ,тг}.

Легко видеть, что

Поскольку в случае события Ап П B(n, г, I) величина хп может меняться от (п — 1)г до /, а остальные гг — 1 величины располагаются на отрезке [0,яп — г] и должны находиться на расстоянии не менее г, то согласно предположению индукции

Тем самым лемма доказана.

Чтобы убедиться в справедливости утверждения теоремы 15 достаточно заметить, что /(/с, г) = f(k, г, 1).

Тем самым теорема 15 доказана.

Следующая теорема описывает асимптотическое поведение функции f{k,r).

Теорема 16. Пусть г* — последовательность вещественных чисел, такая, что 0 ^ г* ^ 1/(к — 1). Тогда

Доказательство. Пусть = о(к) при к оо. Воспользовавшись вторым замечательным пределом, легко получить

Рассмотрим случай, когда 1/г* = о(к2) при к оо.

Это означает, что для некоторой последовательности о* —> оо при к -» оо выполняется г* = ось/к2. Поскольку г* ^ 1 /(к — 1), то достаточно рассмотреть два подслучая: а* ~ с * /с, где с — константа не превышающая 1, и а* = б(Аг). В первом подслучае

Так как во втором подслучае (к — 1)а*/А: = д(к), то согласно (2.16)

Рассмотрим случай, когда 1/г* ~ ск2 при к -? оо, где с = const. Поскольку (к — 1)/ск = о(А:), то согласно (2.16)

И наконец, рассмотрим случай, когда к2 = о(1/г*) при к -* оо. Это означает, что для некоторой последовательности а* —» 0 при к оо выполняется г* = а*/Аг. Поскольку - 1)а*/А; = д(к), то согласно (2.16)

Тем самым, теорема 16 доказана.

Отсюда следует, что если в нашем распоряжении имеется объем памяти размера с • А;2, то доля библиотек мощности fc, для которых описанным алгоритмом мы можем находить ответ за 6 элементарных операций, равна е-1/с. А если в нашем распоряжении имеется объем памяти больший по порядку, чем А:2, то для почти всех библиотек мы можем находить ответ за 6 элементарных операций. С другой стороны, если у нас имеется объем памяти, меньший по порядку, чем А:2, то почти всегда мы не сможем воспользоваться описанным выше алгоритмом поиска.

Обозначим через d(k) среднее значение описанной выше величины c/(^i,... ,?*), тогда справедливо следующее утверждение.

Теорема 17. d(k) = 1 /(к2 - 1).

Доказательство. Обозначим через F(x) функцию распределения случайной величины d(?i,... ,?*).

Тогда так как при х ^ 0 имеем F(x) = 0, а при х ^ 1/(& — 1) имеем F(x) = 1, то используя формулу интегрирования по частям, нетрудно получить

Тем самым теорема 17 доказана.

Отсюда следует, что в типичной ситуации достаточно иметь к2 памяти, чтобы обеспечить время поиска в 6 элементарных операций.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >