Обсуждение участника:NikitaMarkovnikov — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Теорема |id = Th1 |about = о близких запросах в сплей-дереве |statement = Пусть в сплей-дерево слож...»)
(нет различий)

Версия 18:39, 28 апреля 2014

Теорема (о близких запросах в сплей-дереве):
Пусть в сплей-дерево сложены ключи [math] 1, \dotsc, n [/math], зафиксируем один из ключей [math] f [/math], пусть выполняется [math] m [/math] запросов к ключам. Тогда суммарное время на запросы есть [math] \displaystyle O(n \log_{2} n + m + \sum_{i=1}^{m} \log_2 ( \lvert q_{i} - f \rvert + 1)) [/math], где [math] q_{i} [/math][math] i [/math]-й запрос.
Доказательство:
[math]\triangleright[/math]

Для доказательства теоремы воспользуемся методом потенциалов:

[math] a_{i} = t_{i} + \Phi_{i} - \Phi_{i-1} [/math]

По условию выполняется [math] m [/math] запросов, следовательно

[math] T = \displaystyle \sum_{i=1}^{m} t_{i} = \sum_{i=1}^{m} \left(a_{i} + \Phi_{i-1} - \Phi_{i} \right) = \sum_{i=1}^{m} a_{i} + \Phi_{0} - \Phi_{m} = \sum_{i=1}^{m} a_{i} + \Delta \Phi [/math] [math] (\ast) [/math]

Для удобства введем обозначения:

  1. Весом узла с ключом [math] q [/math] будем называть величину [math] w(q) =\displaystyle \frac {1}{\left(\lvert q - f \rvert + 1 \right )^{2}} [/math].
  1. Размером узла, содержащего ключ [math] q [/math], будем называть величину [math] s(q) = \displaystyle \sum_{y} w(y) [/math], где [math] y [/math] — узлы поддерева с корнем в [math] q [/math].
  1. [math] r(q) = \log_{2}s(q) [/math] — ранг узла.
  1. Потенциал дерева обозначим как [math] \Phi = \displaystyle \sum_{q=1}^{n} r(q) = \displaystyle \sum_{q=1}^{n} \log_{2}s(q) [/math].

Пусть [math] W [/math] — вес дерева. Тогда [math] W = \displaystyle \sum_{q=1}^{n} w(q) = \sum_{q=1}^{n} \frac {1}{\left(\lvert q - f \rvert + 1 \right)^{2}} \leqslant 2 \cdot \sum_{q=1}^{+\infty} \frac {1}{ \left ( \lvert q - f \rvert + 1 \right)^{2}} = O(1) [/math].

Из определения размера узла следует, что [math] w(q) \leqslant s(q) \leqslant W [/math].

Также заметим, что для любого [math] q [/math] от [math] 1 [/math] до [math] n [/math] верно [math] w(q) \geqslant \displaystyle \frac {1}{n^{2}} [/math].

Тогда изменение потенциала

[math] \Delta\Phi \leqslant \displaystyle \sum_{q=1}^{n} \log_{2} W - \sum_{q=1}^{n} \log_{2}w(q) = \sum_{q=1}^{n} \log_{2} \frac {W}{w(q)} = O \Biggl(\sum_{q=1}^{n} \log_{2} n^{2}\Biggr) = [/math] [math] \displaystyle O\Biggl(2 \cdot\sum_{q=1}^{n} \log_{2} n\Biggr) = O\left(n \log_{2}n\right) [/math].

Обозначим за [math] t [/math] корень сплей-дерева. Тогда, воспользовавшись вышеуказанной леммой, получаем, что

[math] \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 = [/math] [math] O\left(\log_{2} \left(W \cdot \left(\lvert q - f \rvert + 1 \right)^{2} \right ) \right ) + 1 = O\left(\log_{2} \left(\lvert q - f \rvert + 1 \right) \right ) + 1 [/math]

Тогда, подставляя найденные значения в формулу [math] (\ast) [/math], получаем, что

[math]T=\displaystyle \sum_{i=1}^{m} \left ( O \left( \log_{2} \left ( \lvert q_{i} - f \rvert + 1 \right) \right) + 1 \right ) + O\left ( n \log_{2} n \right) = [/math] [math] \displaystyle O \left (n \log_{2} n + m + \displaystyle \sum_{i=1}^{m} \log_2 \left( \lvert q_{i} - f \rvert + 1 \right) \right)[/math]
[math]\triangleleft[/math]