42
правки
Изменения
Нет описания правки
<tex>O(n V(d)+M S(d)+ TP(d) = O(n V(d) + T(S(d)+P(d)))</tex>,
где <tex>V(d)</tex>, <tex>S(d) </tex> и <tex>P(d) </tex> это оценка времени работы оракулов VolumeQuery, SampleQuery и PointQuery, соответственно.
Выберем <tex>\epsilon : \epsilon_s, \epsilon_p, \epsilon_v \leq \frac{\epsilon^2}{47n}</tex>.
Если все используемые тела являются гиперкубами, то время работы каждого из оракулов составляет в точности <tex>O(d)</tex>, таким образом алгоритм позволяет построить <tex>\epsilon</tex>-аппроксимацию гиперобъема с вероятностью <tex>\geq 3/4</tex> за время <tex>O(\frac{nd}{\epsilon^2})</tex>.
== Примечания Источники==
<references />
