Алгоритм Форда — Фалкерсона

Алгоритм для решения проблемы максимального потока в сети. Он основан на идее увеличения потока путем нахождения дополняющих путей в остаточной сети.

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

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

Алгоритм Хопкрофта-Карпа

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

Алгоритм:
1. Создаем пустое паросочетание и расстояния для каждой вершины, устанавливая их в бесконечность.
2. Используем алгоритм поиска в ширину (BFS) для поиска кратчайших путей от ненасыщенных вершин левой доли к ненасыщенным вершинам правой доли. Обозначим полученные расстояния как d[v], где v - вершина.
3. Запускаем глубинный поиск (DFS) из каждой ненасыщенной вершины левой доли. В ходе DFS осуществляем насыщение вершин в паросочетание, улучшаем текущее паросочетание и снижаем расстояния для каждой рассматриваемой вершины.
4. Повторение до насыщения. Повторяем шаги 2 и 3 до тех пор, пока больше нет насыщенных вершин в правой доле.

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

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

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

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

Сложность: O((n-m+1) * m)
длина текста (n) и длина шаблона (m)

Алгоритм Тарьяна

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

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

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

Алгоритм Косараджу (Косарайю)

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

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

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

Алгоритм Ахо-Корасика

Алгоритм для множественного поиска подстрок в заданном тексте.

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

Сложность: O(n + m + z), где n – длина текста, m – суммарная длина всех шаблонов и z – количество найденных совпадений.

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

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

Алгоритм:
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)