112
правок
Изменения
Закончено описание "Ответ на запрос", исправлены недопонимания с головой. Исправлены пункты 1, 2, 5, 7, 8, 12
{{Определение
|definition='''Каталог''' (англ. ''catalog''){{---}} упорядоченный массив из элементов, на которых введено отношение порядка. В данной статье предполагается, что массив упорядочен по неубыванию.
}}
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>
Итого имеем:
<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>
[[Файл:FCT_pic2.jpg|600px|left|thumb|Построение модифицированных каталогов]]
<br>''Первый этап построения'':
<br>''Второй этап построения'':
<br> Рассмотрим на процесс построения на примере.
<br> Пусть дано <tex> k = 5 </tex> каталогов :
<br> <tex> C_1 = \{1, 3, 6, 7, 11, 12\} </tex>
<br> <tex> C_2 = \{4, 9, 10\} </tex>
=== Ответ на запрос ===
В первом каталоге ответ на запрос найдем с помощью бинарного поиска по <tex> C_1 </tex>. Пусть ответом для этого каталога будет ячейка <tex> cell </tex>. Далее проитерируемся по оставшимся каталогам. Для того, чтобы перейти в новый ''модифицированный каталог '' мы перейдем из <tex> cell </tex> по ссылке влево, чтобы попасть в ''подставную вершину'', а потом из нее перейдем по ссылке вниз, чтобы попасть в следующий каталог. Если теперь <tex> cell </tex> {{--- }} ''неподставная вершина'', то нам достаточно рассмотреть двух ее соседей справа в <tex> C_i </tex>, так как <tex> cell.key < x </tex>, а каждая вторая ячейка из <tex> M_i </tex> попадает в <tex> M_{i - 1} </tex>, т.е. мы бы встретили ее ранееи перешли мы вниз по ней, но это не случилось. Обновив cell осталось максимальным из подходящих значений нужно проверить, что является ли она не''подставным элементом'', если да, то перейдем по ссылке влево, попав в ответ для текущего каталога, иначе это и будет ответ.
