Оценки сложности одного метода решения задачи включающего поиска

В разделе предлагается метод решения задачи включающего поиска, имеющий 3 модификации в зависимости от выбранного базового множества: множества монотонных булевых функций, множества элементарных монотонных конъюнкций и множества булевых переменных. С помощью этого метода получены оценки функций T (k, Sbooh (F> 0)) и Т (к, Sbooly (F, 0)), где в качестве F рассматриваются множества Л4п, /С", Хп. Кроме того, получена асимптотика логарифма среднего значения сложности данного метода. Результаты данного раздела были опубликованы в [41, 43, 163].

В разделе предлагаются 3 алгоритма, которые позволяют для произвольно взятой библиотеки V С В^п строить разрешающие ЗИП I = ь

= (В^п> V, У) информационные графы соответственно над базовыми множествами (Л4^П, 0), (/С^п, 0) и (Х^л, 0). Эти алгоритмы будем обозначать соответственно Pi, Рг > -Рз • Поскольку в задаче включающего.

ь

поиска множество В^п и отношение У фиксированы, то будем считать, что алгоритм Pi (г = 1,2,3) применяется к библиотеке V и результа;

том его применения является разрешающий задачу I = (В^п, У, У) ИГ, который обозначим через Pi (V). Поскольку ИГ P{(V) существенно будет зависеть от порядка следования элементов в библиотеке V, то будем считать, что библиотеки — упорядоченные множества. Каждый ИГ Pi (V) (г = 1,2,3) будет иметь вид дерева, и мы используя в дальнейшем термин дерево, будем подразумевать некоторую его укладку, причем будем считать, что в каждой вершине среди ребер, исходящих из данной вершины, задан некоторый порядок следования, и первое по порядку ребро будем называть самым левым, а последнее — самым правым, и соответственно будем определять понятия левее, правее.

Будем говорить, что функция / покрывает функцию д, если N_g С N_f.

Пусть /, Пересечением конъюнкций fug назовем конъюнкцию переменных, принадлежащих как /, так и у, и обозначим се через f Гд. Таким образом, пересечение fug есть минимальная по числу элементов в характеристическом множестве элементарная монотонная конъюнкция, покрывающая и /, и д. В случае, когда все переменные / отличны от переменных д, будем говорить, что пересечение fug пусто. Через / д обозначим конъюнкцию переменных, принадлежащих /, но не принадлежащих д.

Обозначим через 0 набор, состоящий из всех нулей, т. е. О =.

= (0…0).

Пусть нам дана упорядоченная библиотека V. Обозначим V — = V {0} = {j/i, г/2, • • •, Ук}• Индуктивно опишем процесс построения ИГ P₂(V').

Базис индукции, /^({2/1}) состоит из одного ребра, начало которого является корнем ИГ, а конец — листом, которому приписана запись У, и этому ребру приписана функция ь.

Индуктивный переход. Пусть построен ИГ Рг ({уи • • •, г/i-i}), (* = = 2,3,…, к). Перестраивать его, чтобы он стал допустим для библиотеки {yi,…, j/i}, будем следующим образом.

1. Корень ИГ Pz ({yi, • • •, y*-i}) объявим в качестве текущей вершины р. Объявим g = х ь •.

у i, t

• 2. Будем слева направо просматривать ребра, исходящие из вершины Р до тех пор пока не найдем ребра, пересечение нагрузочной функции которого с функцией g не пусто.
• (a) Если для всех ребер пересечение их нагрузочных функций с g пусто, то из вершины Р выпускаем новое ребро с нагрузочной функцией у, конец ребра объявляем листом и приписываем ему запись у*, и на этом завершаем работу — ИГ ЯгЦуъ • • • I У"}) построен. Здесь, как и везде далее, новое выпускаемое ребро становится самым правым в пучке на данный момент.
• (b) Если же нашлось ребро с нагрузочной функцией /, такой, что пересечение / и g не пусто, то

i. если / = у, то конец этого ребра объявляем листом и приписываем ему запись у", и на этом завершаем работу — ИГ Р₂({у 1,…, у"}) построен;

ii. если //ри / = /Пр, то конец этого ребра объявляем текущей вершиной /?, объявляем g = g f и идем на шаг 2;

ш. если же / ф / П у, то изменим нагрузку рассматриваемого ребра на / П g. Пусть конец этого ребра обозначен через Р отцепим ветвь, растущую из р выпустим из Р' новое ребро и прицепим отцепленную ветвь к концу нового ребра (если вершина 0' была листом, то листом вместе с его нагрузкой становится конец нового ребра) и приписываем новому ребру функцию /(/Пр), после чего если / = р, то объявляем 0' листом, приписываем ей запись у* и завершаем работу, иначе из вершины 0' выпустим еще одно ребро с нагрузкой д (/ П р), конец последнего ребра объявляем листом, приписываем ему запись у, и на этом завершаем работу — ИГ /М{Уь.*., У"}) построен.

Теперь если V ф V то выпустим из корня Рг{У') еще одно ребро и пусть оно будет самым правым, исходящим из корня. Припишем данному ребру функцию тождественная 1, а конец ребра объявим листом и припишем ему запись 0. Полученный ИГ и будет Рг (У).

Заметим, что Рз (У) есть ИГ над базовым множеством (К,^п, 0).

Обозначим Теперь легко описать ИГ P (V). Возьмем вершину и объявим ее корнем, выпустим из нее ребро, которому припишем функцию X ь, а из конца ребра выпустим ветвь, идентичную P2(V). ИГ Pi{V)

построен. Очевидно, что P (V) есть ИГ над базовым множеством Пусть, как и ранее, V — упорядоченная библиотека и V^[1][2] = V{0} = = {уь 2/2, • • •, У к}- Индуктивно опишем процесс построения ИГ P₃(V^r/). Базис индукции. Если.

то P₃({yi}) представляет собой ориентированную цепочку из t ребер, причем начало цепочки есть корень ИГ, конец цепочки — лист с записью yi, a j-му ребру цепочки (j = 1,2,…, t) приписана функция Индуктивный переход. Пусть построен ИГ Рз ({уь…, j/i_i}), (t = = 2,3,…, Аг). Перестраивать его, чтобы он стал допустим для библиотеки {yi,…, 2/^}, будем следующим образом.

объявляем листом, приписываем ему запись у* и завершаем работу — ИГ Рз ({У1, • • • > У*}) построен. Здесь первое ребро новой цепочки становится самым правым, исходящим из 0.

(Ь) Если же нашлось ребро с нагрузочной функцией Xj, покрывающей у, то если д ф Xj, то конец этого ребра объявляем текущей вершиной 0, объявляем д = gxj и идем на шаг 2, иначе конец рассматриваемого ребра объявляем листом, приписываем ему запись у* и завершаем работу — ИГ Рз ({уъ •?•,</"}) построен.

Теперь если V ф V⁷, то выпустим из корня Рз (И') еще одно ребро и пусть оно будет самым правым, исходящим из корня. Припишем данному ребру функцию тождественная 1, а конец ребра объявим листом и припишем ему запись 0. Полученный ИГ и будет Рз (К).

Легко заметить, что по построению каждого из Pi (V'), P2(V)> Рз (У) к произвольной записи у 6 V ведет цепочка ребер, проводимость которой равна Ху, у- Отсюда согласно [28, теорема 1) каждый из ИГ P (V)_y РзОО допустим для библиотеки V.

Через будем обозначать число размещений из п элементов по к. Через W* обозначим множество упорядоченных библиотек из В^п мощности к. Понятно, что |W*| = А^п.

Обозначим.

где i = 1,2,3.

Поскольку все Pi{V) (г = 1,2,3) являются деревьями, то далее часто вместо термина ИГ будем использовать термин дерево.

Следом вершины (3 в дереве D назовем поддерево дерева D, содержащее все ребра, исходящие из вершин, принадлежащих пути, соединяющему корень дерева D с вершиной 0.

Левым следом вершины 0 в дереве D назовем поддерево дерева D, которое состоит из принадлежащих следу вершины 0 ребер, которые в дереве D находятся не правее ребра, принадлежащего пути, соединяющему корень дерева D с вершиной 0.

Библиотекой вершины 0 в дереве D назовем множество записей, приписанных листьям, схемно достижимым из вершины 0.

Вершина дерева называется проходной, если из нее исходит одно ребро.

Лемма 18. Пусть V — произвольная библиотека, D = Pi (V) (i = 2,3), тогда это дерево обладает следующими свойствами:

• 1. Для любой вершины 0 дерева D пересечение любых двух нагрузочных функций, соответствующих ребрам, принадлежащих левому следу вершины 0, всегда пусто.
• 2. Пусть /3 — произвольная вершина дерева D. Пусть Д есть

конъюнкция всех нагрузочных функций, соответствующих ребрам из левого следа вершины /3. Пусть fa = Х{_х • … • ж*_е — функция фильтра вершины 0. Пусть Д /₂ = •… • я*_1+г.

Тогда библиотека вершины 0 содержит все те и только те записи V, которые в разрядах ij (j = 1,2, …,?) имеют 1, а в разрядах ij (j = t -I-1, t + 2,…, t + г) имеют 0.

• 3. Функции фильтров любых двух различных вершин в D различны.
• 4. В дереве каждая проходная вершина является полюсом.

Доказательство. Свойства 1, 2 и 4 достаточно очевидны и следуют из определения Рг (^) и Pz (V), а свойство 3 является следствием свойства 2.

Лемма доказана.

Заметим, что нагрузка ребер в Рг (^) однозначно определяет нагрузку листьев. Поэтому далее мы часто не будем упоминать об нагрузке листьев.

Высотой вершины в дереве назовем длину пути, ведущего из корня в данную вершину.

Напомним, что сложностью вершины /3 в ИГ называется вероятность множества запросов, проходящих в вершину (3, или иными словами сложность вершины /? равна Р (ЛГ^).

Обозначим

Лемма 19. Для любой вершины, находящейся на высоте h в любом дереве D € Vi (г = 2,3), ее сложность не более чем 2″ ^л.

Доказательство. Возьмем произвольное дерево D? T>i (г = 2,3) и рассмотрим произвольную вершину /3> находящуюся на высоте h в D. Поскольку у нас равномерная вероятностная мера, то Р (Л^) = = 2~ⁿN_{fip |. Так как длина пути от корня до вершины /3 равна h, то есть конъюнкция h элементарных монотонных конъюнкций, которые согласно свойству 1 из леммы 18 не пересекаются по переменным. Следовательно, N_4>$ | достигает минимума, когда каждый из h сомножителей (рр является переменной, и тогда |Л^| = 2^П" ^Л откуда и следует утверждение леммы.

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

Пусть D — некоторое дерево, h — натуральное число. Через r (D, h) обозначим число вершин дерева D, находящихся на высоте h.

Лемма 20. Для любого дерева D € Д (i = 2,3) r (D, 1) ^ (*) -I-1 и для любого h € {2,…, п} справедливо r (D, h) ^ (?).

Доказательство. Отметим, что согласно свойству 1 из леммы 18 в любом дереве D € Д (г = 2,3) не может быть вершин, имеющих высоту более п. Обозначим через Т>о множество всех деревьев, нагрузка ребер которых берется из АС^П, таким образом, чтобы удовлетворялось свойство 1 из леммы 18. Пусть D' € Vо — такое дерево, на котором достигается максимум числа вершин, находящихся на высоте h. Покажем, что в D' нагрузка любого ребра, исходящего из вершины, находящейся на высоте менее h, есть переменная. Предположим, что это не так, и имеется ребро, исходящее из вершины, находящейся на высоте менее Л, нагрузка которого содержит по крайней мере 2 переменные х/ и x_q. Заменим нагрузку данного ребра на xi и в ветви, растущей из начала данного ребра, пройдем в самую правую вершину, находящуюся на высоте h — 1, и выпустим из нее ребро с нагрузкой x_q. Понятно, что полученное дерево будет удовлетворять свойству 1 из леммы 18 и иметь большее число вершин, находящихся на высоте /г, чем в D'. Противоречие.

Таким образом, в дереве D' функции фильтров всех вершин, находящихся на высоте /г, являются элементарными монотонными конъюнкциями длины /г. Откуда согласно свойству 3 из леммы 18 число вершин, находящихся на высоте h в дереве D' не больше чем число элементарных монотонных конъюнкций длины Л, т. е. r (D h) ^ ^ (J). Дополнительная 1 при h = 1 появляется из-за ребра с тождественной единицей в качестве нагрузки. А поскольку любое дерево Л, принадлежащее T>i (г = 2,3), принадлежит и 2>о_? ^то утверждение леммы доказано.

Вершину ИГ назовем внутренней, если она нс является полюсом.

Лемма 21. Пусть D € Т>₂, tj — число листьев в дереве D, находящихся на высоте j (j = 1, п). Тогда для любого h € {0, гг — 1}.

h

справедливо г (Л, п — h) ^ 2i~^ht_n-j.

j-0

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

о.

Базис индукции, h = 0. Тогда г (Л, п — 0) ^ 2*~^ht_n-j = t_n.

j-o

Поскольку других вершин кроме листьев на высоте п быть не может, то базис индукции доказан.

Л-1.

Индуктивный переход. Пусть г (Л, п-/г +1) ^ 2^J~^h+1t_n-j. Так.

з=о как в каждую вершину высоты п — h + 1 ведет ребро из вершины высоты n — h, то согласно свойству 4 из леммы 18 на каждую пару вершин высоты n — h + 1 придется самое большее одна внутренняя вершина высоты п — /г, т. е. число внутренних вершин высоты п — h

не превышает.

Учитывая, что у нас есть еще <_п-л листьев, получаем.

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

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

Теорема 29. Если к (п) и т (п) такие числа, зависящие от п, что к —> оо, т (п) = д (п) при п —> оо, то

• при (_m" j) = о (к), к ^ (^) ui = 1,2 справедливо

• при («) ^ к ^ 2(^) справедливо

• при к ж и к ^ 2(^) справедливо

Т (р2, к, п).

Доказательство. Докажем верхнюю оценку для функции Возьмем произвольную библиотеку V € W*. Пусть U — число листьев в дереве P2(V), находящихся на высоте i (i = 1,2,…, n).

Обозначим через di (h) сумму сложностей ребер дерева /^(V), ведущих в вершины высоты нс менее чем h (напомним, что поскольку у нас все ребра предикатные, то сложность ребра есть сложность Обозначим через Pi (V), ведущих в вершины высоты менее чем h. Тогда согласно леммам 19 и 20 имеем начала ребра). Поскольку в вершину высоты г ведет ребро из вершины высоты t — 1, то вспоминая леммы 19 и 21, имеем.

при условии, что h = о (п) при п —> оо.

Если m такая последовательность, что = д (к) и к <, 2(^).

при п —у оо, то возьмем h = тп и тогда.

Если т такая последовательность, что к х (^) и 2(^) < к при п —> оо, то возьмем /i = m + l и тогда.

Из этих соотношений в силу произвольности V получаем требуемую верхнюю оценку.

Верхняя оценка для T (Pi_ik₎n) следует из соотношения Т (Р, к, п) ^ Т (Р2, к, п) + 1. А неравенства.

очевидны.

Нижняя оценка. Согласно теореме 26 для любой ЗИП I = ь

= (?^п, И, У) типа Sbool

где го — число записей веса 0 в библиотеке V.

Если т такая последовательность, что (_да* _х) = о (к) при п —" оо и к ^ (^), то рассмотрим библиотеку V, состоящую только из записей, принадлежащих m-му слою /?^п, тогда для г = 1,2.

поскольку для каждой записи г/ из m-ro слоя Р (0(г/, Ь)) = 2 ^т.

Если т такая последовательность, что к ж (^) при п —> оо и к ^ ^ (^), то рассмотрим библиотеку V, состоящую из всех записей, принадлежащих m-му слою В^п, в которой остальные к — («J записей принадлежат (гаf 1)-му слою В^п, тогда для г = 1,2.

Тем самым нижняя оценка и теорема 29 доказаны.

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

Теорема 30. Если к (п), т (п) и а (п) такие числа, зависящие от п, что

при п —> оо, то для любых таких fc, п.

где ?/'(/, (Х^п, 0)) — множество древовидных ИГ над (Х^п, 0), разрешающих ЗИП /.

Доказательство. Нижняя оценка. В доказательстве теоремы 28 показано, что в условиях теоремы 30 существует та;

ft.

кая задача включающего поиска V — (В^п_уУУ), что IV’I = к и inf T (U) > 2²~^тк. Следовательно,.

Тем самым нижняя оценка доказана.

Верхняя оценка. Возьмем произвольную библиотеку V € W*. Пусть U — число листьев в дереве Рз (У), находящихся на высоте г (г = 1,2.

Не трудно заметить, что число вершин высоты г в дереве Рз (У).

п

не более чем tj- Теперь оценивая число вершин высоты, не мень- j=i

шей, чем m (n), этим числом, а число вершин высоты, меньшей, чем m (n), по лемме 20, и вспоминая, что согласно лемме 19 ребро, ведущее в вершину высоты г, будет иметь сложность, не большую, чем 2^1—*, получим.

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

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

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

Теорема 31. Если к (п) —> со и log₂ к (п) = о (п) при п —> оо, тпо причем Т (/, (Л^^п, 0)) ~ 1 для почти всех ЗИП I G I (fc, Sbooi) —

Доказательство. Пусть s (n) =]31og₂ k (n)[.

Пусть W (n, fc, s) — множество всех библиотек из W^, которые содержат только записи веса, не меньшего, чем s.

Тенью библиотеки V назовем множество.

Нетрудно заметить, что для любой библиотеки V G W (n, к_} s).

Возьмем произвольную библиотеку V G W (n, fc, s). По определению алгоритма Р

где 1{P₂(V)) — количество ребер дерева Р₂(^). Теперь воспользуемся следующим очевидным фактом: если дерево имеет тп вершин, степень инцидентности которых не превышает 2, то в этом дереве не более чем 2т — 2 ребер. Отсюда, вспоминая свойство 4 из леммы 18, имеем.

при п —> оо.

Легко заметить, что при п -> оо справедлива следующая цепочка неравенств

Оценивая сложность библиотек, не принадлежащих W (n, fc,$) через 2к, имеем, что при п оо.

так как если представить log₂ к = п/а_п, где а" —> оо при п —> оо, то при п —> оо.

Учитывая, что T (Pi>k_yn) > Т (к₇ Sbooh (А4^П, 0)) ^ получаем требуемое.

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

Исследуем функцию L = (m, n, t, k) = CJ (?_m)/(*)> ^гА^{е т}> ^п> fc — целые числа и 0 ^ т Oi О < к <�п — t, t <�п.

Лемма 22. Функция L (m, п, ?,&) при фиксированных n, t, k относительно переменной т до точки [tk/n] монотонно возрастает, а после точки [tk/n] 4- 1 монотонно убывает.

Доказательство. Рассмотрим отношение.

Сравним это отношение с 1.

Так как [tk/n] 4- 1 > tk/n > (tk — (п - t — k) — 1)/(n 4- 2), то при m ^ [tk/n] 1 имеем L (m 4- l, n,t, k) < L (m, n, t, k), т.e. функция монотонно убывает.

Так как [tk/n] — 1 < (tk — п)/п < (tk — п + t + к — 1)/(n 4- 2), то при т ^ [tk/n] - 1 имеем L (m 4- 1 , n, t, k) > L (m, n, t, k) или, что-то же самое, при т ^ [tk/n] имеем L (m, n, t, k) > L (m — l, n, t, k), т. е. функция монотонно возрастает.

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

Лемма 23. Пусть т —> оо, к —> со, п —> оо, t оо и т = o (t), т = д (к), к = д (п), t = д (п), тогда

Доказательство. Так как.

при к —> оо, п —? оо и к/п —" 0, то Тем самым лемма доказана.

Лемма 24. Пусть п оо, А: —? оо,? -* оо, ?fc/n —> оо и к = о (п),? = o (n), а = d (tk/n), тогда

Доказательство. Так как tk/n ± а ~ tk/n = о (?) и ffc/n = д (к) при п —> оо, то мы находимся в условиях леммы 23, откуда следует.

Так как.

Асимптотика функции lQ"] 4* a, n, t, lzj находится аналогично и имеет точно такой же вид.

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

Пусть V_n — последовательность библиотек, a s (n) — неубывающая последовательность натуральных чисел, такие, что |У_П| • 2~^а^ -э -" оо при п —^ оо. Скажем, что последовательность библиотек V_n является равномерно распределенной порядка s (n), если в любом п — — s (n)-мерном подкубе куба В^п число записей из V_n асимптотически равно V_n • 2″⁵(^п) при п —У оо.

Лемма 25. Пусть последовательность библиотек V_n — равномерно распределенная порядка s (n), t (n) — неубывающая последовательность натуральных чисел, такая, что t (n) < s (n) и s (n) — — t (n) — неубывающая последовательность, B_tt_n) ~ некоторая последовательность п — t (n) -мерных подкубов куба В^п. Тогда последовательность библиотек V_n П Вц_п) будет равномерно распределенной порядка s (n) — t (n) ?<�а подкубах Вц_пу

Доказательство. В Вц_п) можно выделить 2^П */2^п 3 = 2³/2* непересекающихся подкубов размерности n — s (n). Так как число записей из V_n, содержащихся в каждом из этих подкубов, асимптотически равно |V"| • то V_n П B_t ~ |V^|2— • 2*/2‘ = V_n? 2"* при п —> оо. А так как V_n — равномерно распределенная порядка s (n), то в любом подкубе размерности п — t (n) — (s (n) — t (n)) = п — s (n) куба B_t содержится асимптотически V_n • 2~³ = |У_П|2″⁴ • ~.

~ V_n П Bt • 2"(^3_t) записей при п —> оо.

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

Библиотекой ветви дерева назовем библиотеку корня ветви.

Лемма 26. Пусть последовательность библиотек V_n — равномерно распределенная порядка $(п) ^ 2. Тогда Pi (V_n) (г = 2,3) имеет вид, изображенный на рис. 3.12, и если обозначить через

Рис. 3.12. Дерево равномерно распределенной библиотеки библиотеку дерева D*_n (t = 1,5), то.

Рис. 3.13. Базис индукции.

Доказательство. Докажем сначала, что если s ^ 2, то Pi (V_n) (i = = 2,3) представимо в виде, изображенном на рис. 3.13, где библиотека дерева D" есть библиотека.

Из корня дерева Pi{V_n) (i = 2,3) должно исходить хотя бы одно ребро. Возьмем первое ребро, исходящее из корня. Пусть из этого ребра растет дерево D. Оставшееся поддерево, растущее из корня обозначим D". Предположим, что нагрузочная функция первого ребра равна / = Xj_x • … • Xj_r. По определению алгоритма Рз г = 1. Покажем, что г = 1 и в случае алгоритма Рг. Предположим обратное, т. е., что г ^ 2. Так как s ^ 2, то подкуб Xj_tXj₂ содержит записи из V_n. Так как любая запись из этого подкуба в j разряде содержит «1″, то согласно свойству 2 из леммы 18 она не может принадлежать библиотеке ветви D». Но с другой стороны любая запись из подкуба в j разряде содержит «0», и, значит, не может пройти через фильтр / и соответственно не может принадлежать библиотеке ветви D. Пришли к противоречию, т. е. первому ребру, исходящему из корня приписана переменная. Обозначим ее Xi_t. Согласно свойству 2 из леммы 18 все записи из У_п, содержащие «1″ в ii-м разряде, пройдут по ребру Xi_x, т. е. библиотека дерева D есть V*. Остается заметить, что ни одна запись из V» не пройдет по ребру Xi_x. Тем самым мы доказали, что дерево Pi (V_n) (г = 2,3) представимо в виде, изображенном на рис. 3.13.

Заметим теперь, что согласно лемме 25 последовательность библиотек V" на подкубе х", является равномерно распределенной порядка 5 — 1, и если s — 1 ^ 2, то к V" можно применить это же утверждение.

И вообще, применив к V_n вышеприведенное утверждение s — 1 раз, мы получим требуемое.

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

Если дерево D — ИГ, то через |D| обозначим мощность библиотеки дерева D.

Рис. 3.14. Дерево равномерно распределенной библиотеки порядка 1.

Лемма 27. Пусть последовательность библиотек V_n — равномерно распределенная порядка 1. Тогда Р%{Уп) (* = 2,3) имеет вид, изображенный па рис. 3.14, где |D* | ~ D* ~ |V_n|/2 при п —> оо.

Доказательство. Из корня дерева Pi (V_n) (г = 2,3) должно исходить хотя бы одно ребро. Возьмем первое ребро, исходящее из корня. Пусть из этого ребра растет дерево D. Оставшееся поддерево, растущее из корня обозначим D". Предположим, что нагрузочная функция первого ребра равна / = Xj_x •… • Xj_r. Так как V_n — равномерно распределенная порядка 1, то число записей из V_n, содержащих «I^й в j — 1-м разряде (т. е. принадлежащих подкубу Xj_x) будет асимптотически равно V_n/2. А так как все записи с «1» в ji-м разряде согласно свойству 2 из леммы 18 пройдут по первому ребру, то ветвь, растущая из этого ребра, имеет мощность асимптотически не меньшую, чем |У_п|/2. Но ни одна запись, содержащая «0» в ji-м разряде, не пройдет через фильтр /, а число таких записей (как содержащихся в подкубе Xj_x) асимптотически равно |У_п|/2, т. е. дерево Pi (V_n) (г = 2,3) в самом деле имеет вид, изображенный на рис. 3.14, где |D^| ~ |D?| ~ |1^|/2 при п —> оо.

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

Лемма 28. Для любой библиотеки V С В^п для i = 2,3 выполняется Т (Р_{{У)) < 2V.

Рис. 3.15. Дерево простейшего вида.

Доказательство. Рассмотрим дерево D> имеющее вид, изображенный на рис. 3.15, в котором число ребер, исходящих из корня равно |V|. Вершины, из которых не исходят ребра, являются листьями, и им приписаны взаимно однозначным образом записи из V. Нагрузка ребер дерева D осуществляется функциями из Х^п = {®|,…, х_п} так, что конъюнкция переменных, приписанных каждой из V цепочек совпадает с характеристической функцией тени записи, соответствующей листу, в который данная цепочка ведет.

п — 1.

Поскольку сложность каждой цепочки не больше чем 2^_, <

«=0.

< 2, то T (D) < 2|V|. Теперь остается заметить, что дерево Pi (V) (г = 2,3) можно получить некоторой склейкой ребер дерева D, а, значит, T (Pi (V)) < 2V (г = 2,3).

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

Лемма 29. Пусть последовательность библиотек V_n — равномерно распределенная порядка s (n), где |VJ"|2"*(ⁿ) —> оо при п —> оо. Тогда для г = 2,3 при л —> оо.

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

Базис индукции. s (n) = 1.

Согласно лемме 27 дерево Д (1^_п) (г = 2,3) имеет вид, изображенный на рис. 3.14. Откуда следует, что.

где г — длина элементарной конъюнкции /. Вспоминая леммы 27 и 28, будем иметь.

при п —> оо, т. е. при s=l утверждение леммы справедливо.

Индуктивный переход. Пусть утверждение леммы справедливо для любой равномерно распределенной последовательности библиотек порядка меньшего, чем s (n). Согласно лемме 26 дерево Pi (V_n) (г = 1,2) имеет вид, изображенный на рис. 3.12, и деревья D^г_п есть деревья для библиотек V^, где V" описаны в условии леммы 26 (? = 1, s). Так как согласно лемме 25 доя любого t (n) € {1,5 — 1} последовательность библиотек V* является в своем подкубе Xi_t • … • Xj_t_, • x,_t равномерно распределенной порядка s (n) — t (n) и |V^f| ~ |VJ,|2^-*, при п —^ оо, a V? — равномерно распределенная библиотека порядка 1 в подкубе Xi_x • • Xi_e__t и V* ~ |У_П|2^1-Л при п —У оо, то согласно предположению индукции при i = 1,2 и п оо.

что соответствует предположению индукции.

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

Обозначим через V'(n, A, s, а) — множество неупорядоченных библиотек мощности к таких, что в любом подкубе размерности п — s содержится больше чем [fc • 2″^s] — а и меньше чем [к ? 2~³) + а записей.

Лемма 30. Пусть s (n) —> оо, к (п) • 2"*(^п) —> оо, а (п) = о (к • 2″⁵), к (п) = о (2^п) при п —> оо. Тогда

Доказательство. Обозначим L (m) = L (m, 2^П, 2^П«* А).

Выделим некоторый подкуб размерности п — $(п). Число библиотек, которые в этом подкубе содержат либо не более чем [А: • 2~⁵] — а, либо не менее чем [к • 2~^a] 4- а записей равно.

Если выбросить все эти библиотеки из рассмотрения, то останутся (²_fc) — г библиотек, и все они в рассматриваемом подкубе будут содержать более чем [к • 2″ ^Л] — а и менее чем [/: • 2~^в] + ос записей.

Эту процедуру можно проделать для всех 2^е («) подкубов размерности п — s. Откуда получим, что.

Так как согласно лемме 22 L (m) возрастает до точки [А: • 2″⁵] и убывает после [к • 2~^s] + 1 и так как выполняются условия леммы 24, то.

при п -* оо. Учитывая, что 2*(«) ^ n^2s, при п —> оо имеем.

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

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

Теорема 32. Если log₂ log₂ п = o (log₂ fc (n)) и log₂ к (п) < 2п/3 при п —" оо, то

где i = 2,3.

Доказательство. Пусть W'(гг, А, 5, а) — множество упорядоченных библиотек мощности к таких, что в любом подкубе размерности п — s содержится больше чем [к • 2″³] — а и меньше чем [А: • 2″⁹] + а записей. Так как любую упорядоченную библиотеку можно получить некоторой перестановкой неупорядоченной библиотеки, то.

Подберем параметры следующим образом:

где е = const > 0 такая, что (In к (п) lnn + А:³(п)/4^П)^1+Зс = о (к (п)) при п —> оо. Тогда при п —> оо.

Так как lnfc • Inn + к³/4ⁿ = o (fc), то при п -> оо.

т. е. мы находимся в условиях леммы 30, и любая последовательность библиотек V_n € W'(n, fc (7i), s (n), a (n)) является равномерно распределенной порядка s (n).

Теперь, оценивая сложность библиотек из W'(n, fc, s, а) согласно лемме 29, а библиотек из W* W'(n, fc, s, а) — согласно лемме 28 через 2к (п) и учитывая лемму 30 и соотношения (3.5), (3.6), будем иметь для г = 2,3 при п -> оо.

С другой стороны, оценивая сложность библиотек из множества W* W'(n, A, s, а) через 1, будем для г = 1,2 при гг оо иметь.

Так как при заданных в условии теоремы ограничениях на к log₂(ln/:lnnЬ к³/4ⁿ) = d (log₂&)' то из (3.7) и (3.8) для г = 1,2 при п -> оо будем иметь.

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

• [1] Корень ИГ РзЦуи — iVi-i}) объявим в качестве текущей вершины 0. Объявим g = х ьVi>?.
• [2] Будем слева направо просматривать ребра, исходящие из вершины 0 до тех пор пока не найдем ребро, которому соответствуетпеременная, покрывающая д. (а) Если для всех ребер, исходящих из 0, переменная, соответствующая ребру, не покрывает р, то из вершины 0 выпускаем новую цепочку ребер, аналогичную цепочке, описаннойв базисе индукции, такую, чтобы конъюнкция переменных, приписанных ребрам цепочки, была равна р, конец цепочки