112
правок
Изменения
Добавлено пояснение к второму наивному способу решения задачи, исправлен пункт 9
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>.* Поясняющий пример для второго способа: пусть <tex> C_1 = \{1, 2, 3\}</tex>, <tex> C_2 = \{2, 3, 4\} </tex>, <tex> C_3 = \{1, 3, 4\} </tex>, построим кортежи для каждого значения по определению выше.<br><tex> key_1 = 1 \Leftrightarrow p_1 = \{1, 0, 1\} </tex><br><tex> key_2 = 2 \Leftrightarrow p_2 = \{2, 1, 1\} </tex><br><tex> key_3 = 3 \Leftrightarrow p_3 = \{3, 2, 2\} </tex><br><tex> key_4 = 4 \Leftrightarrow p_4 = \{3, 3, 3\} </tex>. <br> <tex> key_i </tex> - значение, которое попадает в дерево поиска, <tex> p_i </tex> кортеж, которые соответствует <tex> key_i </tex>.
<br> <br>
Итого имеем:
