1632
правки
Изменения
м
== Амортизационный анализ ==* [[Амортизационный анализ. Метод предоплаты]]* [[Саморасширяющийся массив]]* [[Массив с увеличением</уменьшением размера]]* [[Стек]]* [[Очередь]]* [[Список]] == Приоритетные очереди ==* [[Двоичная куча|Двоичная куча]]* [[Биномиальная куча|Биномиальная пирамида]]* [[Фибоначчиевы кучи|Фибоначчиевы кучи]] == Система непересекающихся множеств ==* [[СНМ(наивные реализации) | Наивные реализации]]* [[СНМ(списки с весовой эвристикой) | Списки с весовой эвристикой]]* [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]* [[Анализ реализации с ранговой эвристикой | Анализ реализации с ранговой эвристикой]] == Деревья поиска ==* [[Упорядоченное множество]]* [[Дерево поиска, наивная реализация]]* [[АВЛ-дерево]]* [[2-3 дерево]]* [[B-дерево]]* [[Красно-черное дерево]]* [[Декартово дерево]]* [[Splay-дерево]]* [[Декартово дерево по неявному ключу]]* [[Дерево ван Эмде Боаса]] == Дерево отрезков ==* [[Статистики на отрезках. Корневая эвристика]]* [[Дерево отрезков. Построение]]* [[Реализация запроса в дереве отрезков сверху]]* [[Реализация запроса в дереве отрезков снизу]]* [[Несогласованные поддеревья. Реализация массового обновления]]* [[Многомерное дерево отрезков]]* [[Сжатое многомерное дерево отрезков]] == Дерево Фенвика ==* [[Дерево Фенвика]]* [[Встречное дерево Фенвика]]* [[Дерево Фенвика для некоммутативных операций]]* [[Многомерное дерево Фенвика]] == Хеширование ==* [[Хеширование]]* [[Различные алгоритмы хеширования]]* [[Открытое и закрытое хеширование]]* [[Поиск свободного места при закрытом хешировании]]* [[Хеширование кукушки]]* [[Двойное хеширование]]* [[Перехеширование. Амортизационный анализ]]* [[Фильтр Блума]]* [[Универсальное семейство хеш-функций]] == Сортировка ==* [[Сортировка пузырьком]]* [[Сортировка слиянием]]* [[Cортировка слиянием с использованием O(1) дополнительной памяти]]* [[Сортировка вставками]]* [[Сортировка подсчетом]]* [[Сортировка подсчетом сложных объектов]]* [[Цифровая сортировка]]* [[Поиск k-ой порядковой статистики]]* [[Поиск k-й порядковой статистики за линейное время]]* [[Теорема о нижней оценке для сортировки сравнениями]]* [[Быстрая сортировка]] == [[Сортирующие сети]] ==* [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]* [[Сортирующие сети для квадратичных сортировок]]* [[Сеть Бетчера]] == Алгоритмы поиска ==* [[Троичный поиск]]* [[Поиск с помощью золотого сечения]]* [[Интерполяционный поиск]]* [[Вещественный двоичный поиск]]wikitex>
rollbackEdits.php mass rollback
<wikitex>{{TODO|t= Второй семестр НЕ ОЧЕНЬ ПОНИМАЮ, ЗАЧЕМ ВООБЩЕ ЭТО УТСВЕРЖДЕНИЕ ТУТ}}{{Теорема|statement=Если $f$ — функция ограниченной вариации ($f \in \bigvee(a, b)$), то ее можно представить в виде разности монотонно неубывающих функций ($f = f_1 - f_2$).|proof=Возьмем в качестве $f_1$ функцию $f_1(x) = \bigvee\limits_a^x (f)$, тогда по аддитивности она будет не убывать.Определим как $f_2$ функцию $f_2(x) = f_1(x) - f(x)$. Докажем, что она монотонно не убывает.$a < x_1 < x_2 < b$. Надо доказать, что $f_1(x_1) - f(x_1) \le f_1(x_2) - f(x_2)$, или что $f(x_2) - f(x_1) \le f_1(x_2) - f_1(x_1) = \bigvee\limits_{x_1}^{x_2} (f)$ (используем утверждение 1).Но действительно $f(x_2) - f(x_1) \le | f(x_2) - f(x_1) | \le \bigvee\limits_{x_1}^{x_2} (f)$, ч. т. д. }}
