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

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

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

Алгоритм обратного удаления

Тесно связан с алгоритмом Краскала.

В этом алгоритме мы сортируем все ребра в порядке убывания их весов. После сортировки поочередно выбираем ребра в порядке убывания. Мы включаем текущее выбранное ребро, если исключение текущего ребра приводит к отключению в текущем графе. Основная идея — удалить ребро, если его удаление не приводит к отключению графа.

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

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

Алгоритм Флойда — Уоршелла

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

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

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

Топологическая сортировка

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

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

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

Алгоритм LZW

Метод без потерь для сжатия данных, который основан на построении и использовании словаря. Он был разработан Терри Велчем в 1984 году.

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

Сложность алгоритма LZW зависит от размера исходной строки и размера словаря. В худшем случае: O(n^2), где n - размер строки.

Алгоритм Кнута-Морриса-Пратта

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

1. Создайте массив префиксов (также известный как LPS — самый длинный суффикс префикса), который поможет избежать ненужных сравнений на этапе поиска.
2. Начните сопоставлять шаблон с текстом с самого начала. Используйте два указателя: «i» и «j», чтобы отслеживать позиции.
3. Продолжайте поиск шаблона в тексте, обновляя i и j по мере необходимости.

Алгоритм выводит позиции всех вхождений шаблона в текст.

Сложность: O(N + M)

Алгоритм Рабина-Карпа

Алгоритм поиска строки в тексте, использующий хэш-функции для эффективного сравнения подстроки с искомой строкой.

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

Сложность: O(n + m), где n - длина текста, а m - длина искомой строки. Однако, в худшем случае: O(n * m).

Алгоритм Бойера-Мура

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

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

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

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

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

Алгоритм:
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 - количество итераций.