418
правок
Изменения
→Статическая оптимальность сплей-дерева
Если к ключам <tex>1</tex>, ..., <tex>n</tex>, сложенным в сплей-дерево выполняется <tex>m</tex> запросов, к <tex>i</tex>-му ключу осуществляется <tex>k_i</tex> запросов, где <tex>k_i</tex> > 0, то суммарное время работы не превышает <tex>O(m * H(p_1, p_2, .., p_n))</tex>, где <tex>p_i = k_i / m</tex>, <tex>H</tex> - шенноновская энтропия
|proof=
Известно, что <tex>H(p_1, p_2, .., p_n) = -c * \displaystyle \sum_{i=1}^n (p_i * \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 dpi="130">w(x_i) = p_i =</tex> <tex dpi="180"> {k_i \over m}</tex>, тогда <tex dpi="130">k_i = p_i * 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*m*\log_{2}p_i) = m(1+3r(r)-3 \displaystyle \sum_{i=1}^n p_i\log_{2}p_i) = (*)</tex>
Так как вершина <tex>r</tex> - корень splay-дерева, то очевидно, что <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>, ч.т.д.
}}
