Корневая на строках: различия между версиями
KiKoS (обсуждение | вклад) м (abs fix) |
KiKoS (обсуждение | вклад) м (author) |
||
Строка 16: | Строка 16: | ||
[[Категория:Корневые оптимизации]] | [[Категория:Корневые оптимизации]] | ||
+ | {{Автор|Константин Амеличев|kik0s}} |
Версия 13:43, 18 сентября 2019
Данные идеи очень полезны в задачах, где есть ограничение на суммарный размер строк. Обозначим это ограничение за $\sum |S|$.
Разбиение на длинные и короткие строки
Назовем строку $S \textit{длинной}$, если $|S| \ge \sqrt{\sum |S|}$. Все оставшиеся строки назовем $\textit{короткими}$.
Утверждение:
Существует не более $\sqrt{\sum |S|}$ длинных строк.
Доказательство:
Пусть существует более $\sqrt{\sum | S | }$ длинных строк. Тогда их суммарная длина больше, чем $\sqrt{\sum | S | } \cdot \sqrt{\sum | S | } = \sum | S | $, чего не может быть.
Количество разных длин
Утверждение:
Количество различных длин строк не более, чем $O(\sqrt{\sum |S|})$.
Доказательство:
Пусть количество различных длин равно $x$. Тогда минимальная возможная сумма длин~--- это сумма чисел от 1 до $x$. $$\sum_{i=1}^x i = \frac{x(x + 1)}{2}$$ Так как это число должно быть меньше, чем $\sum |S|$, то $x = O(\sqrt{\sum |S|})$
Автор конспекта: Константин Амеличев
По всем вопросам пишите в telegram @kik0s