234
правки
Изменения
→Алгоритм Грехэма
Добавление каждой точки в ответ занимает <tex>O(n)</tex> времени, всего точек будет <tex>k</tex>, поэтому итоговая сложность <tex>O(nk)</tex>.
= Алгоритм Грехэма Грэхема =
== Описание Алгоритма ==
[[File:Temp.gif|thumb|250px|Промежуточный шаг алгоритма]]1)Находим самую правую нижнюю точку множества <tex>p_0</tex>, добавляем в ответ.2)Сортируем все остальные точки по полярному углу относительно <tex>p_0</tex>.3)Добавляем в ответ <tex>p_1</tex> - самую первую из отсортированных точек.4)Берем следующую по счету точку в массиве <tex>t</tex>. Пока <tex>t</tex> и две последних точке в ответе образуют неправый поворот, удаляем из ответа последнюю точку.5)Делаем п.4, пока не закончатся точки. == Пример Корректность ==
== Псевдокод ==
Подаем в функцию исходное множество S, возвращаем позицию <tex>k</tex> - в <tex>S[1..k - 1]</tex> будет хранится наша оболочка.
<tex>turn(a, b, c)</tex> - модифицированная функция поворота, учитывающая случай, когда точки лежат на одной прямой.
== Сложность ==
Сортировка точек занимает <tex>O(n log n)</tex> времени. При обходе каждая точка добавляется в ответ не более одного раза, поэтому сложность этой части - <tex>O(n)</tex>. Суммарное время - <tex>O(n log n)</tex>.
= Алгоритм Эндрю =
= Алгоритм Чена =
= Алгоритм QuickHull =
