113
правок
Изменения
м
→Память и время работы
Рассмотрим некоторое множество <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>.
