20. Понятие о нижней оценке трудоемкости.

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

Не всегда алгоритм 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). То есть для каждого числа заранее выделена ячейка. При обработке каждое число укладывается в свою ячейку – получается отсортированный набор чисел.