Изменения

Перейти к: навигация, поиск

Динамика по поддеревьям

1 байт убрано, 12:48, 9 декабря 2014
Амортизированные оценки для ДП на дереве
<tex>\forall x \in \left \{ 1 \dots n \right \}: \left | Ch(x) \right | \leqslant n</tex>, поэтому <tex>\sum_{x=1}^n \limits \left | Ch \left ( x \right ) \right |^k \leqslant \sum_{x=1}^n \limits | Ch \left ( x \right ) | \cdot n^{k-1}=n \cdot n^{k-1}=n^k</tex>.
}}
 
==См. Также==

Навигация