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

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

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

Количество диагоналей в n-стороннем выпуклом многоугольнике

Чтобы найти количество диагоналей в n-стороннем выпуклом многоугольнике, можно воспользоваться следующей формулой:

Количество диагоналей = (n * (n - 3)) / 2

Эта формула выведена из того факта, что в выпуклом многоугольнике с n сторонами каждая вершина может быть соединена с любой другой вершиной диагональю, за исключением самой себя, соседних с ней вершин и двух соседних с ними вершин. В результате из каждой вершины можно провести n — 3 диагонали. Однако вы должны разделить это на 2, чтобы не считать каждую диагональ дважды (поскольку, например, соединение вершины A с вершиной B — это то же самое, что соединение вершины B с вершиной A).

Хеширование

— это процесс генерации выходных данных фиксированного размера из входных данных переменного размера с использованием математических формул, известных как хэш-функции.

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

Для этого идеально подходит хеш-таблицы! Их важное свойство состоит в том, что, при некоторых разумных допущениях, все три операции (добавление, удаление, поиск элемента) выполняются за время O(1).

Компоненты хеширования

В основном существует три компонента хеширования:

1. Ключ:
Ключом может быть любая строка или целое число, которое подается в качестве входных данных в хеш-функцию — метод, который определяет индекс или место хранения элемента в структуре данных.

2. Хэш-функция:
Хеш-функция получает входной ключ и возвращает индекс элемента в массиве, называемом хеш-таблицей. Индекс известен как хеш-индекс.

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

Хеш-функции, основанные на делении

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

Хеш-функции, основанные на делении, это самый простой и легкий метод генерации хеш-значения. Хэш-функция делит значение k на M, а затем использует полученный остаток.

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

Минусы:
⁃ Этот метод приводит к снижению производительности, поскольку последовательные ключи сопоставляются с последовательными значениями хеш-функции в хеш-таблице.
⁃ Иногда следует проявлять особую осторожность при выборе значения M.

Метод среднего квадрата для хеш-функции

Метод хеширования, который включает в себя два шага для вычисления хеш-значения:
1. Возведите в квадрат значение ключа k, т.е. k2.
2. Извлеките средние цифры r в качестве значения хеш-функции.

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

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

Метод складывания цифр для хеш-функции

Этот метод включает в себя два этапа:
1. Разделите ключ-значение k на несколько частей, то есть k1, k2, k3,….,kn, где каждая часть имеет одинаковое количество цифр, за исключением последней части, которая может иметь меньше цифр, чем другие части.
2. Добавьте отдельные части. Хэш-значение получается путем игнорирования последнего переноса, если таковой имеется.

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

Метод складывания цифр для хеш-функции

Этот метод включает в себя два этапа:
1. Разделите ключ-значение k на несколько частей, то есть k1, k2, k3,….,kn, где каждая часть имеет одинаковое количество цифр, за исключением последней части, которая может иметь меньше цифр, чем другие части.
2. Добавьте отдельные части. Хэш-значение получается путем игнорирования последнего переноса, если таковой имеется.

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

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

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

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

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

Метод обработки коллизий — метод цепочек

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

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

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

Недостатки:
⁃ Некоторые части хеш-таблицы никогда не используются
⁃ Если цепочка становится длинной, то время поиска в худшем случае может стать O(n).
⁃ Использует дополнительное пространство для ссылок

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

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

Функция, используемая для перехеширования, выглядит следующим образом: 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).