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

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

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

Job Sequencing Problem

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

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

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

Задача о дробном рюкзаке

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

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

Сложность: O(n log n) времени, где n - количество предметов.

Центрированный тип обхода

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

Сложность: O(n), где n - количество узлов в дереве. Каждый узел посещается и обрабатывается ровно один раз.

Прямой тип обхода

Прямой тип обхода является одним из трех базовых типов обхода бинарного дерева. Выполняет обработку узлов в следующем порядке: сначала сам узел, затем его левое поддерево и, наконец, правое поддерево.

Сложность: O(n), где n - количество узлов в дереве. Каждый узел посещается и обрабатывается ровно один раз.

Обратный тип обхода

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

Сложность: O(n), где n - количество узлов в дереве. Каждый узел посещается и обрабатывается ровно один раз.

Обход по порядку уровней бинарного дерева

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

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

Сложность: O(n), где n - количество узлов в дереве. В худшем случае каждый узел будет посещён один раз.

Обход границы на бинарном дереве

Метод обхода бинарного дерева, который проходит по границе дерева в определенном порядке.

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

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

Диагональный обход бинарного дерева

Метод обхода, который выполняется по диагоналям (возрастающей) от верхнего левого узла до нижнего правого узла.

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

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

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

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

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

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

Задача о сумме подмножеств

Задача заключается в нахождении (хотя бы одного) непустого подмножества некоторого набора чисел, чтобы сумма чисел этого подмножества равнялась нулю.

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

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