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

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

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

Массивы

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

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

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

Добавление элемента в конец неотсортированного массива

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

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

Добавление элемента в массив на любую позицию

Чтобы вставить элемент в любую позицию несортированного массива, можно выполнить следующие действия:

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

Сложность: O(n), n - размер массива

Удаление элемента в массиве

Удаление элемента из несортированного массива включает в себя следующие шаги:

1. Найдите индекс удаляемого элемента с помощью линейного поиска.
2. Если элемент не найден, выведите сообщение и выйдите.
3. Сместите элементы после точки удаления на одну позицию влево.

Сложность: O(n), n - размер массива

Генерация подмассивов с использованием рекурсии

Чтобы сгенерировать всевозможные подмассивы, мы используем два указателя start и end для сохранения начальной и конечной точки массива и следуем шагам:

1. Остановитесь, если мы достигли конца массива
2. Увеличьте конечный индекс, если начало стало больше, чем конец.
3. Вывести подмассив от начала индекса до конца и увеличьте начальный индекс.

Сложность: O(n^2), n - размер массива

MO’s Algorithm

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

Термин «МО» происходит от инициалов его изобретателей Миккеля Торупа и Питера М. Олсена.

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

Сложность: O((N+Q)⋅*sqrt(N)), где N — размер массива и Q — количество запросов.

Связанный список

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

В отличие от массивов, связанные списки не требуют смежных ячеек памяти, что обеспечивает динамическое выделение и эффективную вставку и удаление.

Связанный список состоит из узлов, и каждый узел содержит данные и ссылку на следующий узел в последовательности.

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