Алгоритм быстрой оболочки — алгоритм построения выпуклой оболочки на плоскости. Использует идею быстрой сортировки Хоара
Множество точек разбивается на два подмножества, каждое из которых будет содержать одну из ломаных, соединение которых дает многоугольник выпуклой оболочки.
Сложность алгоритма состоит из сложности построения двух подмножеств рассматриваемого множества O(N) и сложностей решения подзадач для каждого из подмножеств: T(N) = T(a) + T(b) + O(N).
В лучшем случае, когда задача разбивается на две равномощные подзадачи, сложность алгоритма является решением рекурсивного уравнения:
(1) T(N) = 2 T(N/2) + O(N) =>
(2) T(N) = O(N log N).
В худшем случае:
(3) T(N) = T(1) + T(N 1) + O(N) =>
(4) T(N) = O(N2).
Лемма Решением уравнения (1) является функция (2) Пусть N = 2k. Тогда T(2k) = 2 T(2k 1) + C 2k ; T(2k 1) = 2 T(2k 2) + C 2k 1 => T(2k) = 4 T(2k 2) + 2 °C 2k 1 + С 2k = 4 T(2k 2) + 2 °C 2k => T(2k) = 2m T(2k m) + m С 2k При m = k (= logN) алгоритм заканчивает работу: T(N) = N T(1) + C logN N = O(N logN)
Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .