Алгоритм Джонсона

Алгоритм для поиска всех элементарных циклов в ориентированном графе.

Алгоритм:
1. Добавьте фиктивную вершину S и проведите ребра из S во все вершины графа. Это позволит учесть все циклы, начинающиеся в любой вершине.
2. Примените алгоритм Беллмана-Форда для определения кратчайших путей из фиктивной вершины S во все остальные вершины графа.
3. Удалите фиктивную вершину S и ребра, идущие из нее.
4. Удачной комбинации нет. Если нашлось ребро (u, v), для которого du + w(u, v) < dv, то граф содержит отрицательный цикл.
5. Создайте новый ориентированный граф, где ребра соответствуют кратчайшим путям, найденным в предыдущем шаге.
6. Примените алгоритм поиска в глубину (DFS) для каждой вершины, чтобы найти все элементарные циклы в новом графе.

Сложность: O(V^3 + VE)

Алгоритм Кадане

Алгоритм для решения задачи о максимальной сумме подмассива.

Алгоритм:
1. Инициализируйте переменные maxendinghere и maxsofar равными первому элементу массива.
2. Пройдитесь по всем элементам массива, начиная со второго элемента.
3. Для каждого элемента, вычислите maxendinghere как максимум из текущего элемента и суммы текущего элемента и maxendinghere.
4. Если maxendinghere больше maxsofar, обновите maxsofar.
5. Повторите шаги 3-4 для всех элементов массива.
6. Верните значение maxsofar, которое будет содержать максимальную сумму подмассива.

Сложность: O(n), где n – количество элементов в массиве.

Кратчайший путь с одним источником в направленных ациклических графах

Задача нахождения кратчайшего пути от одной вершины ко всем остальным вершинам в графе.

Алгоритм:
1. Инициализируйте расстояния от источника до всех остальных вершин графа бесконечно большими значениями, кроме расстояния от источника до самого себя, которое равно нулю.
2. Создайте очередь с приоритетом, в которой будут храниться вершины, и положите в нее источник.
3. Пока очередь с приоритетом не пуста извлеките вершину из очереди с приоритетом, установите ее как текущую вершину и пройдитесь по всем смежным вершинам текущей вершины:
⁃ Если новое расстояние (расстояние от источника до текущей вершины + вес ребра до смежной вершины) меньше текущего расстояния до смежной вершины, обновите расстояние.
⁃ Если смежная вершина еще не была посещена, добавьте ее в очередь с приоритетом.
4. Верните расстояния от источника до всех остальных вершин.

Сложность: O((V + E) log V)

Нахождение максимального паросочетания в двудольном графе

Задача поиска наибольшего множества попарно несмежных ребер, таких что каждая вершина графа является концом не более чем одного ребра из этого множества.

Алгоритм:
1. Разделите вершины графа на две доли.
2. Инициализируйте пустое множество паросочетания.
3. Пока есть непомеченные вершины:
- Выберите непомеченную вершину из первой доли и запустите поиск в глубину (DFS) из этой вершины.
- В процессе DFS для каждой непомеченной вершины во второй доле:
* Если вершина не принадлежит паросочетанию, добавьте ребро между текущей вершиной и найденной вершиной в паросочетание.
* Если вершина принадлежит паросочетанию, найдите альтернативную цепь с помощью попеременного обхода паросочетания и пометьте все вершины этой цепи.
4. Верните множество паросочетания.

Сложность: O(V * E)

Алгоритм Миллера-Рабина

Алгоритм для проверки чисел на простоту. Он основан на принципе ферматовских свидетелей и позволяет с высокой вероятностью определить, является ли число простым или составным.

Алгоритм:
1. Представьте число n в виде n-1 = 2^s * d, где d нечетное.
2. Выберите случайное целое число a в интервале [2, n-2].
3. Вычислите a^d mod n.
4. Если (a^d) mod n = 1 или (a^d) mod n = n-1, перейдите к следующему шагу.
5. Для i от 1 до s-1:
- Вычислите (a^(2^i * d)) mod n.
- Если (a^(2^i * d)) mod n = n-1, перейдите к следующему шагу.
- Если (a^(2^i * d)) mod n = 1, то число n является составным.
6. Если ни в одном из шагов выше не было обнаружено свидетелей простоты, то число n с высокой вероятностью является простым. В противном случае, число n является составным.

Сложность: O(k * log^3(n))

Алгоритм Монте-Карло

Метод статистических вычислений, основанный на генерации случайных чисел. Он используется для аппроксимации или оценки значения некоторой функции, или для проверки выполнения некоторого условия на основе статистических данных.

Сложность алгоритма Монте-Карло зависит от количества итераций, проводимых для получения достаточно точного результата. Чем больше итераций, тем точнее будет оценка или аппроксимация. Однако, сложность алгоритма часто зависит от сложности самой задачи или функции, которую нужно оценить. В общем случае, сложность алгоритма Монте-Карло может быть оценена как O(N), где N - количество итераций.

Алгоритм масштабирования пропускной способности

Алгоритм для решения проблемы максимального потока в графе. Он основан на алгоритме Форда-Фалкерсона.

Алгоритм:
1. Найдите начальный поток в графе, например, с использованием алгоритма Форда-Фалкерсона.
2. Инициализируйте пропускную способность масштабирования - это максимальная пропускная способность ребер в графе.
3. Пока пропускная способность масштабирования больше нуля:
- Выполните DFS (поиск в глубину) или BFS (поиск в ширину) для нахождения увеличивающего пути от источника к стоку в графе с пропускной способностью, которая превышает текущую пропускную способность масштабирования.
- Если найден увеличивающий путь:
- Найдите минимальную пропускную способность c увеличивающего пути.
- Увеличьте поток по увеличивающему пути на значение c.
- Уменьшите пропускную способность масштабирования на значение c.
4. Верните итоговый поток в графе.

Сложность: O((V+E) * logC), где C - максимальная пропускная способность ребер в графе

Алгоритм Эдмондса-Карпа

Алгоритм поиска максимального потока минимальной стоимости.

Алгоритм:
1. Инициализируйте поток во всех ребрах графа нулем.
2. Пока существует увеличивающий путь в остаточной сети:
- Выполните поиск в ширину или в глубину для нахождения увеличивающего пути от источника к стока в остаточной сети.
- Если найден увеличивающий путь:
- Найдите минимальную пропускную способность c увеличивающего пути.
- Увеличьте поток по увеличивающему пути на значение c.
- Уменьшите поток по обратным ребрам на значение c.
3. Верните итоговый поток в графе.

Сложность: O(V * E^2)

Алгоритм Диница

Алгоритм для решения задачи о максимальном потоке в графе.

Алгоритм:
1. Начните с построения уровней для текущего графа потока.
2. Выполните DFS (поиск в глубину) для поиска путей в остаточной сети от стартовой вершины.
- Если увеличивающая цепь не найдена, переместитесь на следующий уровень вершин.
- Если увеличивающая цепь найдена, найдите минимальную пропускную способность c увеличивающей цепи.
- Обновите поток и ребра.
3. Верните итоговый поток в графе.

Сложность: O(V^2 *E)

Сумма конечных узлов в графе

Метод простой суммы, используется для вычисления суммы элементов в конечной последовательности.

Чтобы применить алгоритм суммы конечных узлов, нужно
1. Найти конечные узлы
2. Сохранить их значение
3. Сложить все значения

Поиск высоты дерева

Высота дерева - это количество уровней в дереве, начиная с корневого узла.

Алгоритм:
1. Если дерево пустое (не содержит узлов), то его высота равна 0.
2. Иначе, если дерево содержит узлы:
- Рассмотрим левое поддерево и вычислим его высоту с помощью рекурсивного вызова этого же алгоритма.
- Рассмотрим правое поддерево и вычислим его высоту с помощью рекурсивного вызова алгоритма.
- Высота дерева будет максимальной высотой из левого и правого поддеревьев, увеличенной на 1.

Метод скользящего окна

алгоритмический подход, который применяется для решения задач, связанных с обработкой последовательных данных. Он основывается на применении фиксированного окна переменной ширины, которое "скользит" по последовательности данных, выполняя определенные операции на каждом шаге.

Алгоритм:
1. Инициализируем начало окна и конец окна.
2. Пока конец окна не достигнет конца последовательности данных, выполняем следующие шаги:
- Выполняем операции над элементами внутри текущего окна.
- Перемещаем окно вправо, увеличивая начало и конец окна на один элемент.
- Обновляем результат, если необходимо.
3. Возвращаем итоговый результат.

Сложность: O(n), где n - общее количество элементов в последовательности данных.

Алгоритм Кана

Алгоритм топологической сортировки графа. Он позволяет упорядочить вершины графа таким образом, чтобы для каждого ребра из вершины u в вершину v, вершина u предшествовала вершине v в сортировке.

Алгоритм:
1. Создайте пустой список упорядоченных вершин.
2. Найдите и сохраните все вершины графа, которые не имеют входящих ребер (вершины с нулевой входящей степенью) во временный список.
3. Пока временный список не пуст:
- Извлеките вершину u из временного списка и добавьте ее в конец упорядоченного списка.
- Для каждого ребра (u, v), исходящего из вершины u:
- Уменьшите входящую степень вершины v на 1.
- Если входящая степень вершины v становится нулевой, добавьте вершину v во временный список.
4. Если упорядоченный список содержит все вершины графа, верните его как результат топологической сортировки. Иначе, граф содержит циклы и топологическая сортировка невозможна.

Сложность: O(V + E)

Добавление элементов в бинарное дерево поиска

Операция, которая позволяет вставить новый элемент в дерево, сохраняя его структуру упорядоченной.

Алгоритм:
1. Если дерево пустое, создайте новый узел и сделайте его корневым.
2. Иначе, начните с корневого узла и сравните значение нового элемента со значением текущего узла.
3. Если значение нового элемента меньше значения текущего узла, перейдите к его левому поддереву.
- Если левого поддерева нет, создайте новый узел и сделайте его левым потомком текущего узла.
- Иначе, перейдите в левое поддерево и повторите шаги с пункта 2.
4. Если значение нового элемента больше или равно значению текущего узла, перейдите к его правому поддереву.
- Если правого поддерева нет, создайте новый узел и сделайте его правым потомком текущего узла.
- Иначе, перейдите в правое поддерево и повторите шаги с пункта 2.

Сложность: O(log n)

Поиск вершины по значению в бинарном дереве

Операция, которая позволяет найти узел с определенным значением в структуре дерева.

Алгоритм:
1. Начните с корневого узла.
2. Сравните значение искомого элемента с значением текущего узла.
- Если значения совпадают, значит, узел найден.
- Если значение искомого элемента меньше значения текущего узла, перейдите к его левому поддереву.
- Если значение искомого элемента больше значения текущего узла, перейдите к его правому поддереву.
3. Повторите шаги 2 и 3 до тех пор, пока не будет найден узел с искомым значением или пока не будет достигнут конец дерева (узел не найден).

Сложность: O(log n)

Удаление вершины по значению из бинарного дерева

Операция, которая позволяет удалить узел без потомков из структуры дерева.

Краткий алгоритм удаления конечной вершины из бинарного дерева:
1. Найдите в дереве вершину, которую надо удалить.
2. Если узел со значением, которое нужно удалить, является конечным (т.е. не имеет потомков), то удалите этот узел.

Сложность: O(log n)

Удаление вершины по значению из бинарного дерева

Операция, которая позволяет удалить узел без потомков из структуры дерева.

Краткий алгоритм удаления узла, который имеет левое ИЛИ правое поддерево:
1. Найдите в дереве вершину, которую надо удалить.
2. Если у узла есть только левое/правое поддерево, то заменить родителю удаляемого узла ссылку на левое/правое поддерево.

Сложность: O(log n)

Удаление вершины по значению из бинарного дерева

Операция, которая позволяет удалить узел без потомков из структуры дерева.

Краткий алгоритм удаления узла, который имеет как левое, так и правое поддерево:
1. Найдите в дереве вершину, которую надо удалить.
2. Если у узла есть и левое, и правое поддерево, найти наибольший (или наименьший) элемент в левом (или правом) поддереве.
3. Заменить значение удаляемого узла значением найденного элемента.
4. Удалить найденный элемент из левого (или правого) поддерева.

Сложность: O(log n)

Z-алгоритм

Алгоритм находит все вхождения шаблона в тексте.

Идея состоит в том, чтобы объединить шаблон и текст и создать строку «P$T», где P — это шаблон, $ — специальный символ, который не должен присутствовать в шаблоне и тексте, а T — это текст. Создайте массив Z для объединенной строки. В массиве Z, если значение Z в любой точке равно длине шаблона, то шаблон присутствует в этой точке.

Сложность: O(m + n), где длина текста равна n, а шаблона — m

Job Sequencing Problem

Комбинаторная оптимизационная задача, которая заключается в распределении выполнения работ с определенными сроками сдачи и прибылями, чтобы максимизировать общую прибыль.

Алгоритм:
1. Сортируем работы по убыванию прибыли.
2. Создаем массив длиной равной максимальному сроку сдачи работ, заполняем его -1, чтобы отметить свободные слоты.
3. Проходимся по отсортированным работам:
- Для каждой работы ищем наибольший возможный слот с сроком сдачи до или равным текущему сроку сдачи работы.
- Если найден свободный слот, помещаем работу в этот слот и устанавливаем значение слота на индекс этой работы.
4. Восстанавливаем последовательность работ, проходясь по массиву слотов. Работы, у которых значение слота не равно -1, добавляем в итоговую последовательность.

Сложность: O(n log n)