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

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

Сложность: 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)

Раскраска графов

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

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

Сложность: O(n^2), где n - количество вершин в графе.

Гамильтонов цикл

Гамильтонов цикл — это цикл в графе, который посещает каждый узел ровно один раз и возвращается в начальный узел.

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

Сложность: O(N!), где N — количество вершин.

Подсчет инверсий

Счетчик инверсий для массива указывает, насколько далеко (или близко) находится массив от сортировки. Если массив уже отсортирован, то счетчик инверсий равен 0, но если массив отсортирован в обратном порядке, счетчик инверсий будет максимальным.

Алгоритм:
1. Создайте функцию merge, которая подсчитывает количество инверсий при слиянии двух половин массива.
⁃ Создайте два индекса i и j, i — индекс первой половины, а j — индекс второй половины.
⁃ Если a[i] больше, чем a[j], то происходят инверсии (mid – i), поскольку левый и правый подмассивы отсортированы, поэтому все оставшиеся элементы в левом подмассиве (a[i+1], a[i +2] … a[mid]) будет больше, чем a[j].
2. Создайте рекурсивную функцию, чтобы разделить массив пополам и найти ответ, суммируя количество инверсий в первой половине, количество инверсий во второй половине и количество инверсий путем слияния двух.

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

Выпуклая оболочка с использованием алгоритма Джарвиса

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

Алгоритм:
1. Инициализируйте p как крайнюю левую точку.
2. Делаем следующее, пока не возвращаемся к первой (или крайней левой) точке:
⁃ Следующая точка q — это точка такая, что тройка (p, q, r) направлена ​​против часовой стрелки для любой другой точки r.
⁃ Чтобы найти это, мы просто инициализируем q как следующую точку, а затем проходим через все точки.
⁃ Для любой точки i, если i больше против часовой стрелки, т. е. ориентация (p, i, q) против часовой стрелки, то мы обновляем q как i.
⁃ Нашим окончательным значением q будет точка, расположенная крайним против часовой стрелки.
⁃ next[p] = q (сохраните q как следующее из p в выходной выпуклой оболочке).
⁃ p = q (установите p как q для следующей итерации).

Сложность: O(m * n), где n — количество входных точек, а m — количество выходных точек или точек оболочки (m <= n).

Выпуклая оболочка с использованием алгоритма «разделяй и властвуй»

Алгоритм:
1. если в наборе всего 3 или меньше точек, вычислите и верните их выпуклую оболочку напрямую.
2. Разделить: найти точку с наименьшей координатой X (а в случае ничьей — наименьшую координату Y) и точку с наибольшей координатой X (а в случае ничьей — наибольшую координату Y). . Эти две точки вместе с линией, соединяющей их, делят набор точек на верхнее и нижнее подмножество.
3. Рекурсия: рекурсивно найти выпуклые оболочки верхнего и нижнего подмножеств. Эти две выпуклые оболочки представляют собой части выпуклой оболочки выше и ниже разделительной линии.
4. Слияние: объедините верхнюю и нижнюю выпуклые оболочки, чтобы получить окончательную выпуклую оболочку.

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

Касательные между двумя выпуклыми многоугольниками

Чтобы найти касательные между двумя выпуклыми многоугольниками, вы можете выполнить следующие общие шаги.

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

Сложность: O(n1 log (n1) + n2 log(n2))

Динамическая выпуклая оболочка

Динамическая выпуклая оболочка — это расширение проблемы выпуклой оболочки, которое позволяет эффективно вставлять и удалять точки в наборе, сохраняя при этом выпуклую оболочку.

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

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

Сложность: O(n*q), где q — количество добавляемых точек.

Проверка многоугольника на выпуклость

Подход к проверке:

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

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

Метод умножения для хеш-функции

Этот метод включает в себя следующие шаги:
1. Выберите постоянное значение A такое, чтобы 0 < A < 1.
2. Умножьте значение ключа на A.
3. Извлеките дробную часть кА.
4. Умножьте результат предыдущего шага на размер хеш-таблицы, т.е. M.
5. Результирующее значение хеш-функции получается путем принятия нижнего значения результата, полученного на шаге 4.

Плюсы:
Преимущество метода умножения в том, что он может работать с любым значением от 0 до 1, хотя есть некоторые значения, которые дают лучшие результаты, чем остальные.

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

Метод обработки коллизий — метод открытой адресации (Линейное зондирование)

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

Функция, используемая для перехеширования, выглядит следующим образом: rehash(key) = (n+1)%table-size

Пусть h(x) — номер ячейки, вычисленный с помощью хэш-функции, а S — размер таблицы:

Если ячейка h(x) % S заполнена, мы пытаемся (h(x) + 1) % S
Если (h(x) + 1) % S также заполнена, то (h(x) + 2) % S
Если (h(x) + 2) % S также заполнена, то (h(x) + 3) % S и тд.

Метод обработки коллизий — метод открытой адресации (Квадратичное зондирование)

Этот метод также известен как метод среднего квадрата. В этом методе мы ищем i^2 -й слот на i-й итерации. Мы всегда начинаем с исходного местоположения хеша. Если занята только локация, то проверяем остальные слоты.

Пусть h(x) будет индексом слота, вычисленным с использованием хеш-функции.

Если слот h(x) % S заполнен, мы пытаемся (h(x) + 1*1) % S
Если (h(x) + 1*1) % S также заполнен, то (h(x) + 2*2) % S
Если (h(x) + 2*2) % S также заполнено, то (h(x) + 3*3) % S

Метод обработки коллизий — метод открытой адресации (Двойное хеширование)

В этом методе приращения зондирующей последовательности вычисляются с использованием другой хэш-функции. Мы используем другую хеш-функцию h2(x) и ищем слот i*h2(x) в i-м повороте.

Пусть h(x) будет индексом слота, вычисленным с использованием хеш-функции.

Если слот h(x) % S заполнен, мы пробуем (h(x) + 1*h2(x)) % S
Если (h(x) + 1*h2(x)) % S также заполнено, то (h(x) + 2*h2(x)) % S
Если (h(x) + 2*h2(x)) % S также заполнено, то мы пробуем (h(x) + 3*h2(x)) % S

Понимание вычислительной сложности

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

Вот несколько способов найти ручку и порядок О:
1. O(n^2): Вы идете и спрашиваете первого человека в классе, есть ли у него ручка. Кроме того, вы спрашиваете этого человека о других 99 людях в классе, есть ли у них эта ручка и так далее. Это то, что называется O(n^2).
2. O(n): пойти и опросить каждого ученика индивидуально — это O(N).
3. O(log n): Теперь делим класс на две группы и спрашиваем: «Ручка на левой или на правой стороне класса?» Затем берем эту группу, и снова делим на две, спрашиваем еще раз и так далее. Повторяем процесс, пока у нас не останется один ученик, у которого будет ручка. Это то, что подрузамивается под O (log n).