355
правок
Изменения
→Время работы
<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>
<tex> E(\operatorname{deg_{S_k}} (\operatorname{nn} (q, S_{k+1}))) \le6 \cdot \frac {1} {C^{|R_{k+1}|}_{|R_k|}} \sum_sum\limits_{R'_{k+1}\subset R_k} \sum_frac {a_j1} {|R_{k+1}|} \sum\limits_{a_i\in R'_{k+1}} \operatorname{deg_{R_k}} (a_ja_i)\cdot 6 = \frac {6} {C^{|R_{k+1}|}_{|R_k|} \cdot |R_{k+1}|} \sum\limits_{R'_{k+1}\subset R_k} \sum\limits_{a_i\in R'_{k+1}} \operatorname{deg_{R_k}} (a_i) =
6 \cdot \frac {\sum_{a_i\in R_k} \operatorname{deg}(a_i)} {|R_k|} = O(1)
</tex>
