355
правок
Изменения
→Время работы
|statement=Для заданной точки <tex>q</tex> на <tex>k</tex>-ом уровне средняя степень ближайшей на <tex>k+1</tex>-ом уровне вершины равна <tex>O(1)</tex>.
|id=nearestdegreelemma
|proof={{TODO|t=proofКажется, я вообще не понимаю, что тут происходит, поэтому просто перепишу, что есть}} <tex> \frac {\sum_{R'_{k+1}\subset R_k} \operatorname{deg_{R_k}}(nn(R'_{k+1}[-1], R'_{k+1}))} {C^{|R_{k+1}|}_{|R_k|} |R_{k+1}|!} =\frac {\sum_{R'_{k+1}\subset R_k} \frac {1} {|R_{k+1}|} \sum_{a_i \in R'_{k+1}} \operatorname{deg_{R_k}} (nn(a_j,R'_{k+1}\backslash\{a_i\})) } {C^{|R_{k+1}|}_{|R_k|}} = \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}|} \le6 \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)</tex>
}}
{{Лемма
