http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=217.66.152.124&* 2026-04-27T16:23:42Z Вклад участника MediaWiki 1.30.0 http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D1%85%D0%BD%D0%B8%D0%BA%D0%B0_%D1%87%D0%B0%D1%81%D1%82%D0%B8%D1%87%D0%BD%D0%BE%D0%B3%D0%BE_%D0%BA%D0%B0%D1%81%D0%BA%D0%B0%D0%B4%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F&diff=61047 2017-05-29T22:01:29Z

<p>217.66.152.124: Добавлен первый способ решения</p> <hr /> <div>'''Техника частичного каскадирования''' (англ. ''fractional cascading technique'') {{---}} это способ организации структуры данных, который предназначен для быстрого итеративного поиска в &lt;tex&gt; k &lt;/tex&gt; каталогах.<br /> <br /> {{Задача<br /> |definition = Дано &lt;tex&gt; k &lt;/tex&gt; каталогов &lt;tex&gt; C_i &lt;/tex&gt;, каталог &lt;tex&gt;i&lt;/tex&gt; представляет собой упорядоченный массив размера &lt;tex&gt; n_i &lt;/tex&gt;. Поступают запросы, которые представляют собой один элемент &lt;tex&gt; x &lt;/tex&gt;. Требуется для каждого запроса определить в каждом каталоге элемент меньше либо равный &lt;tex&gt; x &lt;/tex&gt;. <br /> }}<br /> <br /> == Различные подходы к решению ==<br /> <br /> Пусть &lt;tex&gt; n = \sum\limits_{i = 1}^k n_i &lt;/tex&gt;.<br /> &lt;br&gt;<br /> 1) Пусть пришел запрос &lt;tex&gt; x &lt;/tex&gt;. Пробежимся по всем каталогам. Пусть мы находимся в &lt;tex&gt; i&lt;/tex&gt;-ом каталоге, тогда мы можем ответить на запрос для данного каталога за &lt;tex&gt; O(\log n_i) &lt;/tex&gt; используя бинарный поиск. Так как каталогов &lt;tex&gt; k &lt;/tex&gt; штук, то в итоге мы обработаем запрос за &lt;tex&gt; O(k \log n) &lt;/tex&gt;. Для хранения всех каталогов понадобится &lt;tex&gt; \Theta(n) &lt;/tex&gt; памяти.<br /> &lt;br&gt;</div>

217.66.152.124