Изменения

Известно, что <tex>H(p_1, p_2, .., p_n) = -c * \cdot \displaystyle \sum_{i=1}^n (p_i * \cdot \log_{2}p_i)</tex> - шенноновская энтропия.<br>Пусть <tex>s(x) = \displaystyle \sum_{y} w(y)</tex> {- количество вершин в поддереве с корнем в x. А <tex>r(x) = \log_{2} s(x)</tex> - ранг вершины.<br>Обозначим за <tex>r</tex> корень splay-дерева}} шенноновская энтропия.Из предыдущей теоремы известно, что <tex>a_{splay} \leqslant 1+3(r(r)-r(x))</tex><br>

Пусть <tex>s(x) = \displaystyle \sum_{y} w(y)</tex> {{---}} количество вершин в поддереве с корнем в <tex>x</tex>. А <tex>r(x) = \log_{2} s(x)</tex> {{---}} ранг вершины. Обозначим за <tex>r</tex> корень <tex>splay</tex>-дерева.Из предыдущей теоремы известно, что <tex>a_{splay} \leqslant 1+3(r(r)-r(x))</tex> Пусть <tex dpi="130">w(x_i) = p_i =</tex> <tex dpi="180"> {k_i \over m}</tex>, тогда <tex dpi="130">k_i = p_i * \cdot m</tex>.<br><tex>m+3mr(r)-3 \displaystyle \sum_{i=1}^n k_ir(x_i) \leqslant m+3mr(r)-3 \displaystyle \sum_{i+1}^n k_i\log_{2}w(x_i) =</tex> <tex> m+3mr(r)-3 \displaystyle \sum_{i=1}^n (p_i*\cdot m*\cdot \log_{2}p_i) = m(1+3r(r)-3 \displaystyle \sum_{i=1}^n p_i\log_{2}p_i) = (*)</tex>Так как вершина <tex>r</tex> {{--- }} корень <tex>splay</tex>-дерева, то очевидно, что <tex>s = \displaystyle \sum_{y} w(y) = 1</tex>, следовательно <tex>r(r) = \log_{2}s(r)=0</tex>. Поэтому <tex>(*) = m(1+H(p_1,...,p_n)) = O(mH(p_1,...,p_n))</tex>, ч.т.д.