Подбор констант

Материал из Algocode wiki
Версия от 20:39, 22 октября 2019; Глеб (обсуждение | вклад) (Новая страница: «В корневой декомпозиции очень важен размер блока. Обычно брать s = $\sqrt{N}$ или близкое к ней...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

В корневой декомпозиции очень важен размер блока. Обычно брать s = $\sqrt{N}$ или близкое к ней число(желательно, чтобы делилось на максимально возможную степень двойки) оптимально, но сейчас мы поговорим об особых случаях. Пусть s - размер блока и мы знаем, что алгоритм работает за $O(N * s + \frac{N ^ 2 * \log(N)}{ s})$, тогда если взять s = $\sqrt{N} * 4$, то алгоритм будет работать быстрее, чем при s = $\sqrt{N}$, то есть при определении размера блока первым делом надо смотреть на асимптотику.

$O(n \sqrt{n \log n})$