Алгоритмика
/
CS
Анализ алгоритмов
Вычислительная сложность
Асимптотический анализ
Мастер-теорема
Сортировки
Сортировка пузырьком
Сортировка выбором
Сортировка вставками
Сортировка кучей
Сортировка подсчетом
Цифровая сортировка
Бинпоиск и интерактивки
Бинарный поиск
Бинарный поиск по ответу
Последовательности
Сжатие координат
Декомпозиция задач
Сканирующая прямая
Откатывание состояний
Корневые эвристики
Алгоритм Мо
Meet-in-the-middle
Арифметика
Битовое представление чисел
Векторизация
Структуры данных
Базовые структуры данных
Массивы и кортежи
Итераторы
Динамический массив
Двоичная куча
Деревья поиска
Деревья в STL
Декартово дерево
Неявный ключ
Структуры для множеств
Битсет и битовое сжатие
Система непересекающихся множеств
Запросы на отрезках
Префиксные суммы
Дерево Фенвика
Разреженная таблица
Корневые структуры
Персистентность
Структуры с откатами
Метод копирования пути
Персистентное дерево отрезков
Персистентное декартово дерево
Дерево отрезков
Дерево отрезков на указателях
Отложенные операции
Отложенное построение
Динамическое программирование
Общие приёмы динамики
Динамика по подотрезкам
Ленивая динамика
Комбинаторная оптимизация
Жадные алгоритмы
Матроиды
Метод отжига
Пересчет динамики по слоям
Оптимизация через разделяй-и-властвуй
Оптимизация Кнута
Convex Hull Trick
Дискретный метод Лагранжа
Теория игр
Игра «Ним»
Математика
Алгебра
Бинарное возведение в степень
Матрицы
Задачи на умножение матриц
Линейные уравнения
Многочлены
Интерполяция
Алгоритм Карацубы
Быстрое преобразование Фурье
Модулярная арифметика
Алгоритм Евклида
Расширенный алгоритм Евклида
«Деление» по модулю
Факторизация и простые числа
Решето Эратосфена
Ро-алгоритм Полларда
Графы
Обходы графов
Хранение графов
Поиск в глубину
Поиск компонент связности
Двудольные графы и раскраски
Нахождение цикла
Топологическая сортировка
Эйлеров цикл
Мосты и точки сочленения
Компоненты сильной связности
2-SAT
Кратчайшие пути
Пути в ациклических графах
Поиск в ширину
Алгоритм Дейкстры
Связность и остовные деревья
Лемма о безопасном ребре
Алгоритм Прима
Алгоритм Краскала
Алгоритм Борувки
Динамическая связность
Корневые деревья
Запросы на деревьях
Связь задачи LCA и static RMQ
Метод двоичных подъемов
Центроидная декомпозиция
Heavy-light декомпозиция
Паросочетания
Лемма Бержа
Алгоритм Куна
Задачи на паросочетания
Теорема о свадьбах
Потоки
Поток минимальной стоимости
Геометрия
Геометрические примитивы
Точки и вектора
Скалярное и векторное произведение
Прямые и отрезки
Многоугольники
Выпуклые оболочки
Применения выпуклых оболочек
Алгоритм Джарвиса
Алгоритм Грэхэма
Алгоритм Чана
Верхние и нижние огибающие
Строки
Поиск подстроки
Префикс-функция
Z-функция
Алгоритм Манакера
Хеширование
Полиномиальное хеширование
Коллизии хешей
Проверки на изоморфизм
Строковые структуры
Префиксное дерево
Алгоритм Ахо-Корасик
Дерево палиндромов
Суффиксный массив
Разное
Численные методы
Метод Ньютона
Методы Монте-Карло
Технологии программирования
Стресс-тестирование
Просто интересные задачи
Последовательности
Последовательности
В этой главе рассматриваются алгоритмы для неотсортированных последовательностей.
← Бинарный поиск по ответу
← ../Бинпоиск и интерактивки
Сжатие координат →
../Декомпозиция задач →