Интернет магазин китайских планшетных компьютеров

Компьютеры - Алгоритм Киркпатрика - Сложность алгоритма

Проверка принадлежности точки A многоугольнику P2 выполняется за время O. В каждом из двух рассмотренных случаев время выполнения соответствующего алгоритма равно O. Таким образом общая сложность алгоритма построения выпуклой оболочки объединения двух выпуклых многоугольников составляет O. Отсюда заключаем, что в соотношении T 2T + f: f = O, значит решением соотношения является T = O, что и определяет сложность алгоритма.