2. Построение выпуклой оболочки. Нижняя оценка трудоемкости.

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

1) Поиск всех ребер оболочки. Ребро – отрезок, соединяющий две исходных точки таким образом, что все остальные точки лежат по одну сторону от этого отрезка. Перебор всех пар точек и проверка условия занимает O(n^3) времени.

2) Алгоритм Джарвиса

3) Алгоритм Грэхема

Дополнение к 1):

а) можно перебирать все треугольники. Построенные на 3-х точках, если внутри есть точка - она не крайняя, на поиск одной точки и проверку O(n^3) времени, всего точек n значит общая оценка O(n^4).

б) если найти крайнюю точку, затем перебирать треугольники постоенные на этой точке, то вместо 3х вершин перебираем 2, следовательно общая оценка O(n^3).

Трудоемкость решаемой задачи определяется как О(Х), где Х – число, предел отношения которого не ноль и не бесконечность.

Не всегда алгоритм 1 O(n^2) медленнее алгоритма 2 O(nlogn). В случае, если количество вершин m выпуклой оболочки постоянно (не зависит от общего количества точек n), то время будет себя вести как O(n). Рационально при условии m

Докажем, что нельзя решить задачу построения выпуклой оболочки быстрее, чем за O(nlogn).

Если было бы возможно построить выпуклую оболочку за время t, то и сортировку набора чисел можно было бы провести за t (задача построения оболочки не проще).

Пусть есть набор чисел Xi>0, построим Xi^2, поставим им в соответствие точки(парабола).

Построим выпуклую оболочку.

Выпишем номера точек, в том порядке, в каком они встречаются в выпуклой оболочке, начиная с крайней левой вершины.

Таким образом, за время O(n)+ Т(n), где Т(n)-время построения выпуклой оболочки, решена задача сортировки. Следовательно O(n)+ Т(n)>= O(nlogn).

Т(n)>= O(nlogn).

Оценка снизу задачи построения выпуклой оболочки - O(nlogn).

Если все множество чисел, с которыми мы работаем, конечно, то сортировка проводится за O(n). То есть для каждого числа заранее выделена ячейка. При обработке каждое число укладывается в свою ячейку – получается отсортированный набор чисел.