algo

Здесь представлено 145 алгоритмов. Ко всем алгоритмам даны краткие описания и программы на C++.

Показать: последние добавленные, последние редактированные алгоритмы.

Вы также можете скачать PDF-книгу, в которой все статьи собраны в виде одного большого файла.

Алгебра (23)

элементарные алгоритмы (20)

• Функция Эйлера и её вычисление ^[TeX]
• Бинарное возведение в степень за O (log N) ^[TeX]
• Алгоритм Евклида нахождения НОД (наибольшего общего делителя) ^[TeX]
• Решето Эратосфена ^[TeX]
• Расширенный алгоритм Евклида ^[TeX]
• Числа Фибоначчи и их быстрое вычисление ^[TeX]
• Обратный элемент в кольце по модулю ^[TeX]
• Код Грея ^[TeX]
• Длинная арифметика ^[TeX]
• Дискретное логарифмирование по модулю M алгоритмом baby-step-giant-step Шэнкса за O (sqrt(M) log M) ^[TeX]
• Диофантовы уравнения с двумя неизвестными: AX+BY=C ^[TeX]
• Модульное линейное уравнение первого порядка: AX=B ^[TeX]
• Китайская теорема об остатках. Алгоритм Гарнера ^[TeX]
• Нахождение степени делителя факториала ^[TeX]
• Троичная сбалансированная система счисления ^[TeX]
• Вычисление факториала N! по модулю P за O (P log N) ^[TeX]
• Перебор всех подмасок данной маски. Оценка 3^N для суммарного количества подмасок всех масок ^[TeX]
• Первообразный корень. Алгоритм нахождения ^[TeX]
• Дискретное извлечение корня ^[TeX]
• Решето Эратосфена с линейным временем работы ^[TeX]

сложные алгоритмы (3)

• Тест BPSW на простоту чисел за O (log N)
• Эффективные алгоритмы факторизации: Полларда p-1, Полларда p, Бента, Полларда Монте-Карло, Ферма
• Быстрое преобразование Фурье за O (N log N). Применение к умножению двух полиномов или длинных чисел ^[TeX]

Графы (51)

элементарные алгоритмы (4)

• Поиск в ширину ^[TeX]
• Поиск в глубину
• Топологическая сортировка ^[TeX]
• Поиск компонент связности ^[TeX]

компоненты сильной связности, мосты и т.д. (4)

• Поиск компонент сильной связности, построение конденсации графа за O (N + M) ^[TeX]
• Поиск мостов за O (N + M) ^[TeX]
• Поиск точек сочленения за O (N + M) ^[TeX]
• Поиск мостов в режиме онлайн за O(1) в среднем ^[TeX]

кратчайшие пути из одной вершины (4)

• Алгоритм Дейкстры нахождения кратчайших путей от заданной вершины до всех остальных вершин за O (N² + M) ^[TeX]
• Алгоритм Дейкстры для разреженного графа нахождения кратчайших путей от заданной вершины до всех остальных вершин за O (M log N) ^[TeX]
• Алгоритм Форда-Беллмана нахождения кратчайших путей от заданной вершины до всех остальных вершин за O (N M) ^[TeX]
• Алгоритм Левита нахождения кратчайших путей от заданной вершины до всех остальных вершин за O (N M)

кратчайшие пути между всеми парами вершин (2)

• Нахождение кратчайших путей между всеми парами вершин графа методом Флойда-Уоршелла за O (n³) ^[TeX]
• Подсчёт количества путей фиксированной длины между всеми парами вершин, нахождение кратчайших путей фиксированной длины за O (n³ log k) ^[TeX]

минимальный остов (5)

• Минимальное остовное дерево. Алгоритм Прима за O (n²) и за O (m log n) ^[TeX]
• Минимальное остовное дерево. Алгоритм Крускала за O (M log N + N²)
• Минимальное остовное дерево. Алгоритм Крускала со структурой данных 'система непересекающихся множеств' за O (M log N)
• Матричная теорема Кирхгофа. Нахождение количества остовных деревьев за O (N³)
• Код Прюфера. Формула Кэли. Количество способов сделать граф связным ^[TeX]

циклы (3)

• Нахождение отрицательного цикла в графе за O (N M) ^[TeX]
• Нахождение Эйлерова пути или Эйлерова цикла за O (M)
• Проверка графа на ацикличность и нахождение цикла за O (M)

наименьший общий предок (LCA) (5)

• Наименьший общий предок. Нахождение за O (sqrt (N)) и O (log N) с препроцессингом O (N)
• Наименьший общий предок. Нахождение за O (log N) с препроцессингом O (N log N) (метод двоичного подъёма)
• Наименьший общий предок. Нахождение за O (1) с препроцессингом O (N) (алгоритм Фарах-Колтона и Бендера)
• Задача RMQ (Range Minimum Query - минимум на отрезке). Решение за O (1) с препроцессингом O (N)
• Наименьший общий предок. Нахождение за O (1) в режиме оффлайн (алгоритм Тарьяна) ^[TeX]

потоки и связанные с ними задачи (10)

• Алгоритм Эдмондса-Карпа нахождения максимального потока за O (N M²)
• Метод Проталкивания предпотока нахождения максимального потока за O (N⁴)
• Модификация метода Проталкивания предпотока за O (N³)
• Поток с ограничениями
• Поток минимальной стоимости (min-cost-flow). Алгоритм увеличивающих путей за O (N³ M)
• Задача о назначениях. Решение с помощью min-cost-flow за O (N⁵)
• Задача о назначениях. Венгерский алгоритм (алгоритм Куна) за O (N³) ^[TeX]
• Нахождение минимального разреза алгоритмом Штор-Вагнера за O(N³) ^[TeX]
• Поток минимальной стоимости, циркуляция минимальной стоимости. Алгоритм удаления циклов отрицательного веса ^[TeX]
• Алгоритм Диница нахождения максимального потока ^[TeX]

паросочетания и связанные с ними задачи (6)

• Алгоритм Куна нахождения наибольшего паросочетания за O (N M) ^[TeX]
• Проверка графа на двудольность и разбиение на две доли за O (M)
• Нахождение наибольшего по весу вершинно-взвешенного паросочетания за O (N³)
• Алгоритм Эдмондса нахождения наибольшего паросочетания в произвольных графах за O (N³) ^[TeX]
• Покрытие путями ориентированного ациклического графа ^[TeX]
• Матрица Татта. Рандомизированный алгоритм для поиска максимального паросочетания в произвольном графе ^[TeX]

связность (3)

• Рёберная связность. Свойства и нахождение ^[TeX]
• Вершинная связность. Свойства и нахождение ^[TeX]
• Построение графа с указанными величинами вершинной и рёберной связностей и наименьшей из степеней вершин ^[TeX]

К-ые пути (0)

обратные задачи (2)

• Обратная задача SSSP (inverse-SSSP - обратная задача кратчайших путей из одной вершины) за O (M)
• Обратная задача MST (inverse-MST - обратная задача минимального остова) за O (N M²)

разное (3)

• Покраска рёбер дерева (структуры данных) - решение за O (log N)
• Задача 2-SAT (2-CNF). Решение за O (N + M)
• Heavy-light декомпозиция ^[TeX]

Геометрия (23)

элементарные алгоритмы (10)

• Длина объединения отрезков на прямой за O (N log N)
• Знаковая площадь треугольника и предикат 'По часовой стрелке' ^[TeX]
• Проверка двух отрезков на пересечение ^[TeX]
• Нахождение уравнения прямой для отрезка ^[TeX]
• Нахождение точки пересечения двух прямых ^[TeX]
• Нахождение точки пересечения двух отрезков ^[TeX]
• Нахождение площади простого многоугольника за O (N)
• Теорема Пика. Нахождение площади решётчатого многоугольника за O (1) ^[TeX]
• Задача о покрытии отрезков точками
• Центры тяжести многоугольников и многогранников ^[TeX]

более сложные алгоритмы (13)

• Пересечение окружности и прямой
• Пересечение двух окружностей
• Построение выпуклой оболочки алгоритмом Грэхэма-Эндрю за O (N log N)
• Нахождение площади объединения треугольников. Метод вертикальной декомпозиции
• Проверка точки на принадлежность выпуклому многоугольнику за O (log N)
• Нахождение вписанной окружности в выпуклом многоугольнике с помощью тернарного поиска за O (N log² C)
• Нахождение вписанной окружности в выпуклом многоугольнике методом сжатия сторон за O (N log N) ^[TeX]
• Диаграмма Вороного в двумерном случае, её свойства, применение. Простейший алгоритм построения за O(N⁴) ^[TeX]
• Нахождение всех граней, внешней грани планарного графа за O (N log N) ^[TeX]
• Нахождение пары ближайших точек алгоритмом разделяй-и-властвуй за O (N log N) ^[TeX]
• Преобразование геометрической инверсии ^[TeX]
• Поиск общих касательных к двум окружностям ^[TeX]
• Поиск пары пересекающихся отрезков алгоритмом заметающей прямой за O (N log N) ^[TeX]

Строки (12)

• Z-функция строки и её вычисление за O (N) ^[TeX]
• Префикс-функция, её вычисление и применения. Алгоритм Кнута-Морриса-Пратта ^[TeX]
• Алгоритмы хэширования в задачах на строки
• Алгоритм Рабина-Карпа поиска подстроки в строке за O (N)
• Разбор выражений за O (N). Обратная польская нотация ^[TeX]
• Суффиксный массив. Построение за O (N log N) и применения ^[TeX]
• Суффиксный автомат. Построение за O (N) и применения ^[TeX]
• Нахождение всех подпалиндромов за O (N) ^[TeX]
• Декомпозиция Линдона. Алгоритм Дюваля. Нахождение наименьшего циклического сдвига за O (N) времени и O (1) памяти ^[TeX]
• Алгоритм Ахо-Корасик ^[TeX]
• Суффиксное дерево. Алгоритм Укконена ^[TeX]
• Поиск всех тандемных повторов в строке алгоритмом Мейна-Лоренца (разделяй-и-властвуй) за O (N log N) ^[TeX]

Структуры данных (7)

• Sqrt-декомпозиция ^[TeX]
• Дерево Фенвика
• Система непересекающихся множеств ^[TeX]
• Дерево отрезков ^[TeX]
• Декартово дерево (treap, дерамида)
• Модификация стека и очереди для нахождения минимума за O (1)
• Рандомизированная куча ^[TeX]

Алгоритмы на последовательностях (3)

• Задача RMQ (Range Minimum Query - минимум на отрезке)
• Нахождение наидлиннейшей возрастающей подпоследовательности за O (N²) и O (N log N) ^[TeX]
• K-ая порядковая статистика за O (N)

Динамика (2)

• Динамика по профилю. Задача "паркет"
• Нахождение наибольшей нулевой подматрицы за O (N M) ^[TeX]

Линейная алгебра (3)

• Метод Гаусса решения системы линейных уравнений за O (N³) ^[TeX]
• Нахождение ранга матрицы за O (N³)
• Вычисление определителя матрицы методом Гаусса за O (N³)

Численные методы (3)

• Интегрирование по формуле Симпсона ^[TeX]
• Поиск корней методом Ньютона (касательных) ^[TeX]
• Тернарный поиск ^[TeX]

Комбинаторика (9)

• Биномиальные коэффициенты ^[TeX]
• Числа Каталана ^[TeX]
• Ожерелья ^[TeX]
• Расстановка слонов на шахматной доске
• Правильные скобочные последовательности. Нахождение лексикографически следующей, K-ой, определение номера ^[TeX]
• Количество помеченных графов, связных помеченных графов, помеченных графов с K компонентами связности ^[TeX]
• Генерация сочетаний из N элементов
• Лемма Бернсайда. Теорема Пойа ^[TeX]
• Принцип включений-исключений ^[TeX]

Теория игр (2)

• Игры на произвольных графах. Метод ретроспективного анализа за O (M)
• Теория Шпрага-Гранди. Ним ^[TeX]

Расписания (3)

• Задача Джонсона с одним станком ^[TeX]
• Задача Джонсона с двумя станками ^[TeX]
• Оптимальный выбор заданий при известных временах завершения и длительностях выполнения ^[TeX]

Разное (4)

• Задача Иосифа ^[TeX]
• Игра Пятнашки: существование решения ^[TeX]
• Дерево Штерна-Броко. Ряд Фарея ^[TeX]
• Поиск подотрезка массива с максимальной/минимальной суммой за O(N) ^[TeX]