Корневая декомпозиция: различия между версиями
Материал из Algocode wiki
KiKoS (обсуждение | вклад) (Новая страница: «Рассмотрим следующую учебную задачу: Дан массив $a_1,\ a_2,\ \ldots,\ a_n$. Надо обрабатывать два ти...») |
м |
||
(не показаны 3 промежуточные версии 2 участников) | |||
Строка 1: | Строка 1: | ||
− | + | Иногда в задаче возникают ситуации, когда мы умеем решать ее когда какое-то свойство < $\sqrt{N}$ и больше $\sqrt{N}$. Данный подход и называется корневой декомпозицией(оптимизацией). | |
− | |||
− | |||
− | + | Самыми простыми и наиболее известными применениями данной оптимизации являются : алгоритм проверки на простоту чисел(рассмотрим делители < $\sqrt{N}$ и больше, но так как для любого делителя больше корня можно найти делитель меньше корня => нам надо честно рассмотреть только первые) и например факт, что если суммарная длина строк = $N$, то различных длин строк будет не более $\sqrt{N}$ или если вы увидели ограничение $A B \le N$, то одно из чисел < $\sqrt{N}$. | |
− | |||
− | + | {{Автор|Глеб Лобанов|glebodin}} | |
− | + | [[Категория:Конспект]] | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | {{Автор| | ||
− | [[Категория: |
Текущая версия на 13:45, 11 января 2020
Иногда в задаче возникают ситуации, когда мы умеем решать ее когда какое-то свойство < $\sqrt{N}$ и больше $\sqrt{N}$. Данный подход и называется корневой декомпозицией(оптимизацией).
Самыми простыми и наиболее известными применениями данной оптимизации являются : алгоритм проверки на простоту чисел(рассмотрим делители < $\sqrt{N}$ и больше, но так как для любого делителя больше корня можно найти делитель меньше корня => нам надо честно рассмотреть только первые) и например факт, что если суммарная длина строк = $N$, то различных длин строк будет не более $\sqrt{N}$ или если вы увидели ограничение $A B \le N$, то одно из чисел < $\sqrt{N}$.
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin