81
правка
Изменения
Нет описания правки
Таким образом мы заполнили все наборы за линейное время.
Как уже говорилось ранее после <tex>g</tex> сокращений бит мы получили неконсервативное преимущество в <tex>(h/loglogn)^g</tex>. Мы не волнуемся об этих сокращениях до конца потому, что после получения неконсервативного преимущества мы можем переключиться на лемму два для завершения разделения <tex>q</tex> чисел с помощью <tex>p</tex> чисел на наборы. Заметим, что по природе битового сокращения, начальная задача разделения для каждого набора перешла в <tex>w</tex> подзадачи разделения на <tex>w</tex> поднаборы для какого-то числа <tex>w</tex>.
Теперь для каждого набора мы собираем все его поднаборы в подзадачах в один набор. Затем используя лемму два делаем разделение. Так как мы имеем неконсервативное преимущество в <tex>(h/loglogn)^g</tex> и мы работаем на уровнях не ниже чем <tex>2logloglogn</tex>, то алгоритм занимает <tex>O(qtloglogn/(g(logh - logloglogn) -logloglogn)) = O(loglogn)</tex> времени.
