355
правок
Изменения
→Время работы
|statement=Для заданной точки <tex>q</tex> на <tex>k</tex>-ом уровне средняя степень ближайшей на <tex>k+1</tex>-ом уровне вершины равна <tex>O(1)</tex>.
|id=nearestdegreelemma
|proof={{TODO|t=Кажется, я вообще не понимаю, что тут происходит, поэтому просто перепишу, что есть}}
''Функция <tex>nn</tex> принимает точку и множество и возвращает ближайшего соседа заданной точки из заданного множества.'' <tex> \frac {1} {C^{|R_{k+1}|}_{|R_k|} |R_{k+1}|!} \cdot \sum_{R'_{k+1}\subset R_k} \operatorname{deg_{R_k}}(nn(R'_{k+1}[-1], R'_{k+1}))= </tex>{{TODO|t=А нужна ли нам эта строка?}} Рассмотрим некоторый уровень <tex>S_k</tex>. Определим множество <tex>R_k=S_k\cup\{q\}</tex>. Рассмотрим все возможные подмножества <tex>R_k</tex>, равномощные <tex>R_{k+1}</tex>, тем самым рассмотрев все возможные уровни <tex>k+1</tex>. Для каждой точки из каждого подмножества <tex>R'_{k+1}</tex> рассмотрим степень ближайшей вершины и усредним всё, получив нужную нам оценку. <tex>E(\operatorname{deg_{S_k}} (\operatorname{nn} (q, S_{k+1}))) = \frac {1} {C^{|R_{k+1}|}_{|R_k|} |R_{k+1}|!} =\frac {cdot \sum\sum_limits_{R'_{k+1}\subset R_k} \frac {1} {|R_{k+1}|} \sum_sum\limits_{a_i \in R'_{k+1}} \operatorname{deg_{R_k}} (\operatorname{nn}(a_ja_i,R'_{k+1}\backslash\{a_i\})) } </tex> {C^{TODO|R_{k+1}|t=Кажется, я вообще не понимаю, что тут происходит, поэтому просто перепишу, что есть}_{|R_k|}} = <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}|} =
