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 \cdot \displaystyle \sum_{i=1}^n (p_i \cdot \log_{2}p_i)</tex> {{---}} [[Энтропия_случайного_источника | шенноновская энтропия]].
Пусть <tex>s(x) = \displaystyle \sum_{y} w(y)</tex> {{---}} количество вершин в поддереве с корнем в <tex>x</tex>. А <tex>r(x) = \log_{2} s(x)</tex> {{---}} ранг вершины.
