Изменения

=== Построение ===

Введем определения:

|definition='''Подставной элемент''' {{---}} элемент каталога <tex> M_i </tex>, который пришел из каталога <tex> M_{i + 1} </tex>. А также каталоги <tex> M_i </tex> будем называть '''модифицированными каталогами'''.

}}

Из построения понятно, что мы тратим <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> памяти. По алгоритму понятно, что такая же оценка верна и для времени на предподсчет.

=== Ответ на запрос ===