333
правки
Изменения
→Память и время работы
==Память и время работы ==
Сначала разберемся с памятью. Тут все просто - никаких лишних затрат, кроме как на хранение точек нам требуется, то алгоритм требует <tex> O(n) </tex> памяти.
С временем работы дела обстоят интереснее. На самом деле приведенный алгоритм работает за линейное время. Докажем этот факт.
Рассмотрим некоторое множество <tex> P = \{p_1, ... p_i \} </tex> и точку <tex> q </tex>, которая лежит на границе построенной охватывающей окружности. Тогда попробуем удалить одну точку из набора <tex> P </tex>. Искомая окружность может измениться только в том случае, когда эта удаленная точка лежала на границе, а вероятность этого <tex> 2 / i </tex> (так как точек, которые образуют нашу окружность не более трех. при этом одна из этих трех точек - <tex> q </tex>).
То оценим время работы MinDiscWithPoint c помощью доказанного выше факта. На каждой итераций цикла будет происходить проверка, которая пройдет в "else" с вероятностью <tex> 2 / i </tex>. А сложность работы каждого "else" - <tex> O(i) </tex>. То суммарное время работы MinDiscWithPoint вычисляется следующим образом:
<tex> O(n) + \sum_{i=1}^{n} O(i) * (2 / i ) = O(n) </tex>.
==Источники==
''Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars-Computational Geometry Algorithms and Applications, p. 86
''
