112
правок
Изменения
Добавлена тема "Построение" с небольшим примером
}}
== Различные подходы к решению ==
[[Файл:FCT_pic1.jpg|500px|right|thumb|Пример ответа на запрос]]
Пусть <tex> n = \sum\limits_{i = 1}^k n_i </tex>.
<br>
2) Для второго способа построим сбалансированное бинарное дерево поиска их всех элементов всех каталогов. В каждой вершине дерева будет хранится дополнительно кортеж из <tex> k </tex> элементов - максимальных представителей каталогов меньше либо равных ключу вершины. Таким образом такая структура будет занимать <tex> O(n) </tex> на дерево поиска и <tex> O(kn) </tex> на дополнительные кортежи.Тогда для ответа на запрос <tex> x </tex> найдем в дереве поиска максимальный ключ меньше либо равный <tex> x </tex> и выведем <tex> k </tex> элементов соответствующего кортежа, итого ответ на запрос производится за <tex> O(\log n + k) </tex>.
<br> <br>
Итого имеем :
{| class="wikitable"
|-
| <center>Построение бинарного дерева поиска с кортежами</center> || <center><tex> O(kn) </tex></center> || <center><tex> O(\log n + k) </tex></center>
|}
== Решение с помощью техники частичного каскадирования ==
Как будет показано далее, эта техника берет лучшее от подходов к решению этой задачи, что были рассмотрены выше, а именно она требует <tex> O(n) </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>
=== Построение ===
Рассмотрим подробнее построение каталогов <tex> M_i </tex>.
Введем определения:
{{Определение
|definition='''Подставной элемент''' {{---}} элемент каталога <tex> M_i </tex>, который пришел из каталога <tex> M_{i + 1} </tex>. А также каталоги <tex> M_i </tex> будем называть '''модифицированными каталогами'''.
}}
[[Файл:FCT_pic2.jpg|600px|left|thumb|Построение модифицированных каталогов без ссылок из подставных элементов]]
<br>''Первый этап построения'':
<br> <tex> i = k </tex> : Данный каталог не имеет никаких ссылок и равен <tex> C_i </tex>.
<br> <tex> i < k </tex> : Для построения данного каталога будем сливать каталог <tex> C_i </tex> с каждым вторым элементом каталога <tex> M_{i + 1} </tex>. Каждый элемент из каталога <tex> M_{i + 1} </tex> оснастим ссылкой на позицию, откуда мы его взяли.
<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>
<br> <tex> C_3 = \{1, 2, 7, 8, 11, 12\} </tex>
<br> <tex> C_4 = \{3, 4, 8, 10, 12\} </tex>
<br> <tex> C_5 = \{1, 2, 4, 6, 9\} </tex>
<br> Для наглядности заведем таблицу, где в <tex>i</tex>-ой строке <tex> j </tex>-ая ячейка будет окрашена в зеленый цвет, если она присутствует в каталоге <tex> C_i </tex>. Тогда результатом построения будет таблица, которая представлена на рисунке (без ссылок из ''подставных элементов'').
