Корневая на строках: различия между версиями
KiKoS (обсуждение | вклад) м (latex fix + category) |
KiKoS (обсуждение | вклад) м (abs fix) |
||
Строка 1: | Строка 1: | ||
Данные идеи очень полезны в задачах, где есть ограничение на суммарный размер строк. Обозначим это ограничение за $\sum |S|$. | Данные идеи очень полезны в задачах, где есть ограничение на суммарный размер строк. Обозначим это ограничение за $\sum |S|$. | ||
− | ====Разбиение на | + | ====Разбиение на длинные и короткие строки==== |
− | Назовем строку $S$ | + | Назовем строку $S \textit{длинной}$, если $|S| \ge \sqrt{\sum |S|}$. Все оставшиеся строки назовем $\textit{короткими}$. |
− | |||
{{Утверждение | {{Утверждение | ||
− | |Утверждение=Существует не более $ | + | |Утверждение=Существует не более <nowiki>$\sqrt{\sum |S|}$</nowiki> длинных строк. |
− | |Доказательство=Пусть существует более $ | + | |Доказательство=<nowiki>Пусть существует более $\sqrt{\sum | S | }$ длинных строк. Тогда их суммарная длина больше, чем $\sqrt{\sum | S | } \cdot \sqrt{\sum | S | } = \sum | S | $, чего не может быть.</nowiki> |
}} | }} | ||
+ | |||
====Количество разных длин==== | ====Количество разных длин==== | ||
{{Утверждение | {{Утверждение | ||
− | |Утверждение=Количество различных длин строк не более, чем | + | |Утверждение=<nowiki>Количество различных длин строк не более, чем $O(\sqrt{\sum |S|})$.</nowiki> |
− | |Доказательство=Пусть | + | |Доказательство=<nowiki>Пусть количество различных длин равно $x$. Тогда минимальная возможная сумма длин~--- это сумма чисел от 1 до $x$. $$\sum_{i=1}^x i = \frac{x(x + 1)}{2}$$ Так как это число должно быть меньше, чем $\sum |S|$, то $x = O(\sqrt{\sum |S|})$</nowiki> |
}} | }} | ||
[[Категория:Корневые оптимизации]] | [[Категория:Корневые оптимизации]] |
Версия 13:40, 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|})$