112
правок
Изменения
Синтаксические поправочки ч2
{{Определение
|definition='''Каталог''' {{---}} упорядоченный массив из элементов, на которых введено отношением порядка. В данной статье предполагается, что массив упорядочен по неубыванию.
}}
'''Техника частичного каскадирования''' (англ. ''fractional cascading technique'') {{---}} это способ организации структуры данных, который предназначен для быстрого итеративного поиска в <tex> k </tex> каталогах.
{{Задача
|definition = Дано <tex> k </tex> каталогов <tex> C_i </tex>, каталог <tex>iC_i</tex> представляет собой упорядоченный массив размера имеет размер <tex> n_i </tex>. Поступают запросы, которые представляют собой один элемент <tex> x </tex>. Требуется для каждого запроса определить в каждом каталоге максимальный элемент меньше либо равный <tex> x </tex>.
}}
Пусть <tex> n = \sum\limits_{i = 1}^k n_i </tex>.
<br>
1) Для ответа на запрос последовательно посетим все каталоги. Пусть мы находимся в <tex> i</tex>-ом каталоге, тогда мы можем ответить на запрос для данного каталога за <tex> O(\log n_i) </tex> , используя бинарный поиск. Так как каталогов <tex> k </tex> штук, то в итоге мы обработаем для ответа на запрос за понадобится <tex> O(k \log n) </tex>времени. Для хранения всех каталогов понадобится <tex> \Theta(n) </tex> памяти.
<br>
2) Для второго способа построим сбалансированное бинарное дерево поиска их всех элементов всех каталогов. В каждой вершине дерева будет хранится дополнительно кортеж из <tex> k </tex> элементов - максимальных представителей каталогов меньше либо равных ключу вершины. Таким образом такая структура будет занимать <tex> O(n) </tex> на дерево поиска и <tex> O(kn) </tex> на дополнительные кортежи.Тогда для ответа на запрос найдем в дереве поиска максимальный ключ меньше либо равный <tex> x </tex> и выведем <tex> k </tex> элементов соответствующего кортежа, итого ответ на запрос производится за <tex> O(\log n + k) </tex>.
<br>
Идея данной техники построена на следующем: <br>
1) Мы можем проводить ссылки из каталога номер <tex> i </tex> в <tex> (i + 1) </tex>-ый каталог таким образом, что разница между элементами , соединенными ссылками минимальна, что, очевидно, в некоторых случаях уменьшит время поиска. <br>
2) Мы можем для оптимизации пункта 1 создать модифицированные каталоги <tex> M_i </tex>, где <tex> i </tex>-ый каталог будет представлять каталог <tex> C_i </tex> слитый с <tex> M_{i + 1} </tex>
<br>
