210
правок
Изменения
м
Нет описания правки
Обозначим за <tex> t </tex> корень сплей-дерева. Тогда, воспользовавшись вышеуказанной [[#Lemma1|леммой]] (можно показать, что она верна для любого фиксированного определения веса узла) получаем, что
<tex> \displaystyle a_{i} = 3 \cdot \left( r(t) - r(q_{i}) \right) + 1 = O\left(\log_{2} \frac{s(t)}{s\left(q_{i}\right)}\right) + 1 = O\left(\log_{2} \frac{W}{w(q_{i})}\right) + 1 = </tex> <tex> O\left(\log_{2} \left(W \cdot \left(\lvert q q_{i} - f \rvert + 1 \right)^{2} \right ) \right ) + 1 = O\left(\log_{2} \left(\lvert q q_{i} - f \rvert + 1 \right) \right ) + 1 </tex>.
Докажем, что данное определение потенциала удовлетворяет условию [[Амортизационный анализ|теоремы о методе потенциалов]].
Для любого <tex> i </tex> верно, что <tex> a_{i} = O(\log_{2}(n)) </tex>, так как <tex> \lvert q q_{i} - f \rvert + 1 \leqslant n </tex>, и <tex> \Phi_{i} = O(n\log_{2}(n)) </tex>, как было показано выше. Так как количество операций на запрос <tex>k = O(n) </tex>, то <tex> a_{i} = O(f(k,n)) </tex> и <tex> \Phi_{i} = O(kf(k,n)) </tex>, где <tex> f(k,n) </tex> {{---}} функция из теоремы о методе потенциалов, равная в данном случае <tex> \log_{2}n </tex>. Следовательно потенциал удовлетворяет условию теоремы.
Тогда, подставляя найденные значения в формулу <tex> (\ast) </tex>, получаем, что
