112
правок
Изменения
Добавлены оценки памяти и времени, исправлен пункт 13
|definition='''Каталог''' (англ. ''catalog''){{---}} упорядоченный массив из элементов, на которых введено отношение порядка. В данной статье предполагается, что массив упорядочен по неубыванию.
}}
{{Определение
|definition='''Техника частичного каскадирования''' (англ. ''fractional cascading technique'') {{---}} это способ организации структуры данных, который предназначен для быстрого итеративного поиска в <tex> k </tex> каталогах.
}}
{{Задача
|definition = Дано <tex> k </tex> каталогов <tex> C_i </tex>, каталог <tex>C_i</tex> имеет размер <tex> n_i </tex>. Поступают запросы, которые представляют собой один элемент <tex> x </tex>. Требуется для каждого запроса определить в каждом каталоге максимальный элемент меньше либо равный <tex> x </tex>.
=== Построение ===
Введем определения:
{{ОпределениеОпределения
|definition='''Подставной элемент''' {{---}} элемент каталога <tex> M_i </tex>, который пришел из каталога <tex> M_{i + 1} </tex>. А также каталоги <tex> M_i </tex> будем называть '''модифицированными каталогами'''.
}}
M[i][j].right = M[i][j + 1]
last_non_alien = M[i][j]
Из построения понятно, что мы тратим <tex> O(n_k) </tex> на построение последнего каталога, <tex> O(n_{k-1} + n_k / 2) </tex> на построение предпоследнего и т.д. Пусть <tex> p = 2^{\lfloor log n \rfloor} </tex>. Тогда получаем оценку <tex> O(n_k (1 + 1/2 + 1/4 + ... + 1/p) + n_{k - 1} (1 + 1/2 + 1/4 + ... + 1/(p/2)) + ... + n_1 ) </tex> <tex> = O(2 n_k + 2 n_{k -1} + ... n_1) = O(n) </tex> памяти. По алгоритму понятно, что такая же оценка верна и для времени на предподсчет.
=== Ответ на запрос ===
ans[i] = cell.key
Как можно видеть, для того, чтобы найти ответ для первого каталога необходимо сделать один бинарный поиск, что требует <tex> O(\log n) </tex> времени, после чего необходимо <tex> O(k) </tex> времени, чтобы ответить на запрос для всех остальных каталогов. Суммарное время работы <tex> O(\log n + k) </tex>.
== Ссылки ==
* [http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-12.pdf Fractional Cascading. Bernard Chazelle and Leonidas J. Guibas]
* [http://intsys.msu.ru/magazine/archive/v15(1-4)/pivovarov-205-222.pdf Техника частичного каскадирования для итеративного поиска в линейно упорядоченных множествах А.П. Пивоваров]
