355
правок
Изменения
→Время работы
<tex>E(\operatorname{deg_{S_k}} (\operatorname{nn} (q, S_{k+1}))) = \frac {1} {C^{|R_{k+1}|}_{|R_k|}} \cdot \sum\limits_{R'_{k+1}\subset R_k} \frac {1} {|R_{k+1}|} \sum\limits_{a_i \in R'_{k+1}} \operatorname{deg_{R_k}} (\operatorname{nn}(a_i,R'_{k+1}\backslash\{a_i\})) </tex>
Назовём графом <tex>NN(\{a_i\})</tex> двудольный граф, в левой и правой долях содержащий точки <tex>\{a_i\}</tex>, рёбра <tex>uv</tex> которого означают, что точка <tex>v</tex> является ближайшей для точки <tex>u</tex> (точка <tex>u</tex> лежит в левой доли, точка <tex>v</tex> лежит в правой доли).
Понятно, что <tex>\sum\limits_{a_i \in R'_{k+1}} \operatorname {deg_{R_k}} (\operatorname{nn}(a_i, R'_{k+1}\backslash\{a_i\})) = \sum\limits_{a_i\in R'_{k+1}} \operatorname{deg_{R_k}}(a_i) \cdot \operatorname{deg_{NN(R'_{k+1})}}(a_i)</tex>, так как степень каждой вершины <tex>a_i</tex> учтётся ровно столько раз, сколько рёбер ей инцидентно в правой доли графа <tex>NN</tex>.
<tex>E(\operatorname{deg_{S_k}} (\operatorname{nn} (q, S_{k+1}))) = \frac {1} {C^{|R_{k+1}|}_{|R_k|}} \sum\limits_{R'_{k+1}\subset R_k} \frac {1} {|R_{k+1}|} \sum\limits_{a_i\in R'_{k+1}} \operatorname{deg_{R_k}}(a_i) \operatorname{deg_{NN(R'_{k+1})}}(a_i)</tex>
{{TODO|t=Кажется, я вообще не понимаю, что тут происходит, поэтому просто перепишу, что есть}}
<tex>\frac {\sum_{R'} \sum_{a_j\in R'} \operatorname{deg_{R_k}}(a_j) \cdot \operatorname{deg_{NN(R'_{k+1})}}(a_j)} {C^{|R_{k+1}|}_{|R_k|} \cdot |R_{k+1}|} \le
6 \cdot \frac {\sum_{R'_{k+1}} \sum_{a_j\in R'_{k+1}} \operatorname{deg_{R_k}} (a_j)} {C^{|R_{k+1}|}_{|R_k|} \cdot |R_{k+1}|} =
6 \cdot \frac {\sum_{a_i\in R_k} \operatorname{deg}(a_i)} {|R_k|} = O(1)
