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

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

Константный в худшем случае алгоритм поиска идентичных объектов

Гасанов Э.Э., Луговская Ю.П.
Московский государственный университет,
Российский государственный гуманитарный университет

Резюме:

В работе предлагается алгоритм поиска идентичных объектов, который при затратах памяти порядка $k^2$ почти всегда обеспечивает время поиска в худшем случае в 6 элементарных операций, здесь $k$ – мощность множества, в котором производится поиск.

 

Оглавление


В работе рассматривается задача поиска идентичных объектов в ее геометрической интерпретации, которая звучит следующим образом. Дано конечное подмножество $V=\{y_1,\ldots,y_k\}$ точек из отрезка $[0,1]$ вещественной прямой. Требуется построить условный алгоритм, который для произвольной точки $x\in[0,1)$ (эта точка называется запросом) позволяет найти номер точки из множества $V$, которая совпадает с $x$ (если такая точка в $V$ существует), при условии, что мы умеем выполнять следующие операции над вещественными числами: арифметические операции (сложение, вычитание, умножение, деление, взятие целой части вещественного числа), операции сравнения и возможно некоторые другие простейшие операции. При этом допускается предобработка данных, которая может состоять в сортировке данных (множества $V$), а также в построении некоторых дополнительных структур. Известным алгоритмом решения этой задачи является алгоритм бинарного или дихотомического поиска (см., например, [1, стр.484-492]). Здесь и далее мы будем пользоваться термином "алгоритм", подразумевая "условный алгоритм" (или "относительный алгоритм", см. [2, с. 44-45]). Известно, что время поиска бинарного алгоритма в худшем случае и в среднем равно по порядку $\log_2 k$, а требуемый объем памяти по порядку равен $k$. Здесь под временем поиска понимается количество выполненных элементарных операций, под объемом памяти количество ячеек для хранения вещественных чисел, куда можно поместить данные и дополнительные структуры, а худший случай и среднее берется по множеству всех возможных значений запроса, т.е. по множеству $[0,1)$. В [3] предлагается алгоритм с затратами по памяти порядка $k$, в котором среднее время поиска равно константе, но время поиска в худшем случае имеет порядок $k$. В работах [4,5] предложен алгоритм, который при объеме памяти порядка $k$ позволяет решать задачи в худшем случае за время порядка $\log_2 k$, а в среднем за 2 шага. В данной работе предлагается алгоритм, который для почти всех задач поиска идентичных объектов (т.е. при вариации множества $V$) позволяет при объеме памяти порядка $k^2$ решать задачу в худшем случае за 6 элементарных операций.

Авторы выражают благодарность рецензенту за ценные замечания.


Опишем предлагаемый алгоритм. Пусть нам дано множество $V=\{y_1,$ $y_2,\ldots,y_k\}$, в котором производится поиск. Это множество будем называть библиотекой. Выполним следующую предобработку. Упорядочим точки из $V$ в порядке возрастания и, чтобы не усложнять обозначения, далее считаем, что $y_1<y_2<\dots < y_k$. Находим число $\displaystyle d_V=\min_{2\leq i\leq k}(y_i-y_{i-1})$. Пусть $m=]1/d_V[$ – наименьшее целое, не меньшее, чем $1/d_V$. Выделим место под массив целых длины $m$, и элементы этого массива будем обозначать $n_i$ ( $i=0,1,2,\ldots,m-1$). Разделим отрезок $[0,1]$ на $m$ равных частей:

\begin{displaymath}A_i=[i/m,(i+1)/m),\ i=0,1,\ldots,m-2,\ A_{m-1}=[(m-1)/m,1].\end{displaymath}

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

\begin{displaymath} n_i = \left \{ \begin{array}{ll} -1, & \mbox{\parbox[t]{8cm... ...точки из $V$, которая попала в $A_i$,}} \end{array} \right. \end{displaymath}

где $i=0,1,2,\ldots,m-1$.

После того как сделана данная предобработка, поиск будем осуществлять следующим образом. Пусть нам дан запрос $x\in[0,1)$. Вычислим $j=[x\cdot m]$ – целая часть числа $x\cdot m$. Понятно, что $x\in A_j$. Если $n_j$ равно $-1$, то в библиотеке $V$ нет числа равного $x$. В противном случае сравниваем $y_{n_j}$ с $x$ и если они равны, то номер $n_j$ является ответом задачи, иначе ответ пуст. Тем самым в худшем случае мы выполняем одну операцию умножения, одну операцию взятия целой части, одну операцию сравнения целых чисел, одну операцию сравнения вещественных чисел и две операции извлечения элемента массива, всего 6 операций. Объем памяти, необходимый данному алгоритму, равен сумме объемов массивов целых чисел длины $m$ и вещественных чисел длины $k$. Ниже приводятся результаты, оценивающие величину $m$.

Пусть $k$ – натуральное число, большее 1 и $\xi_1, \xi_2,\ldots, \xi_k$ – независимые равномерно распределенные на отрезке $[0,1]$ случайные величины. Пусть

\begin{displaymath}d(\xi_1,\ldots,\xi_k)=\min_{1\leq i<j\leq k} \vert\xi_i-\xi_j\vert.\end{displaymath}

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

Пусть $r$ – вещественное число и $f(k,r)={\bf P}(d(\xi_1,\ldots,\xi_k)\geq r)$ – вероятность того, что минимальное расстояние между парами различных точек $\xi_i$ ( $i=1,2,\ldots,n$) не меньше $r$.

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

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

 

Теорема 1  

\begin{displaymath}f(k,r)=\left\{ \begin{array}{ll} 1 & \mbox{если $r<0$}\\ (1-... ...q 1/(k-1)$}\\ 0 & \mbox{если $r>1/(k-1)$}. \end{array}\right. \end{displaymath}

Чтобы привести следствие из этой теоремы, описывающее асимптотическое поведение $f(k,r)$, введем обозначения, обычно принятые при описании асимптотических оценок.

Будем писать $\alpha (n)=\bar{o}(1)$, если $\displaystyle \lim_{n\rightarrow \infty}\alpha (n) = 0$.

Будем писать $A(n)=\bar{o}(B(n))$, если $A(n)=B(n)\cdot\bar{o}(1)$.

Скажем, что $A(n)$ асимптотически не превосходит $B(n)$ при $n\rightarrow \infty$ и обозначим $A{\ \stackrel{<}{\scriptstyle\sim}\ }B$, если существует $\alpha (n)=\bar{o}(1)$ такое, что начиная с некоторого номера $n_0$, $A(n)\leq (1+\alpha (n))\cdot B(n)$.

Если $A{\ \stackrel{<}{\scriptstyle\sim}\ }B$ и $B{\ \stackrel{<}{\scriptstyle\sim}\ }A$, то будем говорить, что $A$ и $B$ асимптотически равны при $n\rightarrow \infty$ и обозначать $A\sim B$.

Будем писать $A\stackrel{<}{\scriptstyle\frown} B$, если существует такая положительная константа $c$, что, начиная с некоторого номера $n_0$, $A(n)\leq c\cdot B(n)$.

Если $A\stackrel{<}{\scriptstyle\frown} B$ и $B\stackrel{<}{\scriptstyle\frown} A$, то будем говорить, что $A$ и $B$ равны по порядку при $n\rightarrow \infty$.

 

Теорема 2   Пусть $r_k$ – последовательность вещественных чисел, такая, что $0\leq r_k\leq 1/(k-1)$. Тогда

\begin{displaymath} \lim_{k\rightarrow \infty} f(k,r_k)= \left \{ \begin{array}... ...& \mbox{ если $k^2=\bar{o}(1/r_k)$}.\\ \end{array} \right. \end{displaymath}

Отсюда следует, что если в нашем распоряжении имеется объем памяти размера $c\cdot k^2$, то доля библиотек мощности $k$, для которых описанным алгоритмом мы можем находить ответ за 6 элементарных операций, равна $e^{-1/c}$. А если в нашем распоряжении имеется объем памяти больший по порядку, чем $k^2$, то для почти всех библиотек мы можем находить ответ за 6 шагов. С другой стороны, если у нас имеется объем памяти, меньший по порядку, чем $k^2$, то почти всегда мы не сможем воспользоваться описанным выше алгоритмом поиска.

Обозначим через $\overline{d}(k)$ среднее значение описанной выше величины $d(\xi_1,\ldots,\xi_k)$, тогда справедливо следующее утверждение.

 

Теорема 3   $\overline{d}(k)=1/(k^2-1).$

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


Доказательство теоремы 1.

Пусть $l$ – вещественное число из отрезка $[0,1]$, $r$ – вещественное число, $k$ – натуральное число, большее 1, $n$ – такое натуральное число, что $1\leq n\leq k$. Пусть $x_1, x_2,\ldots, x_k$ – независимые равномерно распределенные на отрезке $[0,1]$ случайные величины. Обозначим через $B(n,r,l)$ событие, что точки $x_1, x_2,\ldots, x_n$ попадают в отрезок $[0,l]$, и минимальное расстояние между парами различных точек $x_i$ ( $i=1,2,\ldots,n$), не меньше $r$. Обозначим через $f(n,r,l)={\bf P}(B(n,r,l))$. Понятно, что если $r<0$, то $f(n,r,l)=l^n$, а при $r>l/(n-1)$, $f(n,r,l)=0$. Поэтому мы будем рассматривать только случай, когда $0\leq r\leq l/(n-1)$.

 

Лемма 1   Если $0\leq r\leq l/(n-1)$, то $f(n,r,l)=(l-(n-1)\cdot r)^n.$

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

Базис индукции. $n=2$.

Поскольку возможны два равновероятных события: случай когда $x_1<x_2$, и когда $x_2<x_1$, то достаточно рассмотреть первую ситуацию и удвоить полученный результат. Поскольку в этом случае $x_1$ может меняться от 0 до $l-r$, а $x_2$ – от $x_1+r$ до $l$, то

\begin{displaymath} f(2,r,l)=2\int_{0}^{l-r} dx_1 \int_{x_1+r}^{l} dx_2=2\int_{0}^{l-r}(l-x_1-r) dx_1=(l-r)^2. \end{displaymath}

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

Через $A_i$ обозначим событие, что случайная величина $x_i$, максимальна среди величин $x_1,\ldots,x_n$, здесь $i=1,\ldots,n$. Понятно, что если $i,j\in\{1,\ldots,n\}$ и $i\ne j$, то $A_i\cap A_j=\emptyset$, кроме того ${\bf P}(A_i)=1/n$, для любого $i\in\{1,\ldots,n\}$. Легко видеть, что

\begin{displaymath}{\bf P}(B(n,r,l))=\sum_{i=0}^n {\bf P}(A_i\cap B(n,r,l))= n\cdot {\bf P}(A_n\cap B(n,r,l)).\end{displaymath}

Поскольку в случае события $A_n\cap B(n,r,l)$ величина $x_n$ может меняться от $(n-1)r$ до $l$, а остальные $n-1$ величины располагаются на отрезке $[0,x_n-r]$ и должны находиться на расстоянии не менее $r$, то согласно предположению индукции

\begin{eqnarray*} f(n,r,l)&=&{\bf P}(B(n,r,l))=n\cdot {\bf P}(A_1\cap B(n,r,l))... ... &=&n\int_{(n-1)r}^{l} (x_n-r-(n-2)r)^{n-1} dx_n=(l-(n-1)r)^n. \end{eqnarray*}



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

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

 

Доказательство теоремы 2.

Пусть $\alpha_k=\bar{o}(k)$ при $k\rightarrow \infty$. Воспользовавшись вторым замечательным пределом, легко получить

$\displaystyle \lim_{k\rightarrow \infty} (1-\frac{\alpha_k}{k})^k$ $\textstyle =$ $\displaystyle \lim_{k\rightarrow \infty} (\frac{k}{k-\alpha_k})^{-k}= \lim_{k\r... ...k-\alpha_k})^{\frac{k-\alpha_k} {\alpha_k}})^{-\frac{k \alpha_k} {k-\alpha_k}}=$  
  $\textstyle =$ $\displaystyle \lim_{k\rightarrow \infty} e^{-\frac{k \alpha_k}{k-\alpha_k}}= \lim_{k\rightarrow \infty} e^{-\alpha_k}.$ (1)

Рассмотрим случай, когда $1/r_k=\bar{o}(k^2)$ при $k\rightarrow \infty$.

Это означает, что для некоторой последовательности $\alpha_k\rightarrow \infty$ при $k\rightarrow \infty$ выполняется $r_k=\alpha_k/k^2$. Поскольку $r_k\leq 1/(k-1)$, то достаточно рассмотреть два подслучая: $\alpha_k\sim c\cdot k$, где $c$ – константа не превышающая 1, и $\alpha_k=\bar{o}(k)$. В первом подслучае

\begin{displaymath}f(k,r_k)=\left(1-\frac{(k-1)\alpha_k}{k^2}\right)^k\sim \left(1-\frac{c(k-1)k}{k^2}\right)^k=\bar{o}(1). \end{displaymath}

Так как во втором подслучае $(k-1)\alpha_k/k=\bar{o}(k)$, то согласно (1)

\begin{displaymath}\lim_{k\rightarrow \infty} f(k,r_k)= \lim_{k\rightarrow \inft... ...k-1)\alpha_k}{k}}= \lim_{k\rightarrow \infty} e^{-\alpha_k}=0. \end{displaymath}

Рассмотрим случай, когда $1/r_k\sim c k^2$ при $k\rightarrow \infty$, где $c=const$.

Поскольку $(k-1)/ck=\bar{o}(k)$, то согласно (1)

\begin{displaymath}\lim_{k\rightarrow \infty} f(k,r_k)= \lim_{k\rightarrow \inft... ...)^k= \lim_{k\rightarrow \infty} e^{-\frac{k-1}{c k}}=e^{-1/c}. \end{displaymath}

И наконец, рассмотрим случай, когда $k^2=\bar{o}(1/r_k)$ при $k\rightarrow \infty$.

Это означает, что для некоторой последовательности $\alpha_k\rightarrow 0$ при $k\rightarrow \infty$ выполняется $r_k=\alpha_k/k^2$. Поскольку $(k-1)\alpha_k/k=\bar{o}(k)$, то согласно (1)

\begin{displaymath}\lim_{k\rightarrow \infty} f(k,r_k)= \lim_{k\rightarrow \inft... ...k-1)\alpha_k}{k}}= \lim_{k\rightarrow \infty} e^{-\alpha_k}=1. \end{displaymath}

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

 

Доказательство теоремы 3.

Обозначим через $F(x)$ функцию распределения случайной величины $d(\xi_1,\ldots,\xi_k)$.

\begin{displaymath}F(x)={\bf P}(d(\xi_1,\ldots,\xi_k)<x)= 1-{\bf P}(d(\xi_1,\ldots,\xi_k)\geq x)=1-f(k,x).\end{displaymath}

Тогда так как при $x\leq 0$ $F(x)=0$, а при $x\geq 1/(k-1)$ $F(x)=1$, то используя формулу интегрирования по частям, нетрудно получить

\begin{eqnarray*} \overline{d}(k)&=&\int_{-\infty}^{\infty} x d F(x)= \int_0^{\f... ...,x) dx=\int_0^{\frac{1}{k-1}} (1-(k-1)x)^k dx= \frac{1}{k^2-1}. \end{eqnarray*}



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


Литература

1
Кнут  Д. Искусство программирования для ЭВМ. Сортировка и поиск. 3, Мир, Москва, 1978.

2
Мальцев  А. И. Алгоритмы и рекурсивные функции. Наука, Москва, 1986.

3
Ершов  А. П. О программировании арифметических операторов. ДАН СССР (1958) 118, 427-430.

4
Гасанов  Э. Э. Мгновенно решаемые задачи поиска. Дискретная математика (1996) 8,  3, 119-134.

5
Гасанов  Э. Э. Функционально-сетевые базы данных и сверхбыстрые алгоритмы поиска. Изд. центр РГГУ, Москва, 1997.

6
Devroye  L. Upper and lower class sequences for minimal uniform spacings. Zeitschrift für Wahrscheinlichkeitstheorie und verwande Gebiete (1982) 61,  2, 237-254.

7
Дейвид  Г. Порядковые статистики. Наука, Москва, 1979, с. 119.


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

Оглавление

Дискретная математика (1999) 11, N 4,

Наверх

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