210
правок
Изменения
Новая страница: «{{Теорема |id = Th1 |about = о близких запросах в сплей-дереве |statement = Пусть в сплей-дерево слож...»
{{Теорема
|id = Th1
|about =
о близких запросах в сплей-дереве
|statement =
Пусть в сплей-дерево сложены ключи <tex> 1, \dotsc, n </tex>, зафиксируем один из ключей <tex> f </tex>, пусть выполняется <tex> m </tex> запросов к ключам. Тогда суммарное время на запросы есть <tex> \displaystyle O(n \log_{2} n + m + \sum_{i=1}^{m} \log_2 ( \lvert q_{i} - f \rvert + 1)) </tex>, где <tex> q_{i} </tex> {{---}} <tex> i </tex>-й запрос.
|proof =
Для доказательства теоремы воспользуемся методом потенциалов:
<tex> a_{i} = t_{i} + \Phi_{i} - \Phi_{i-1} </tex>
По условию выполняется <tex> m </tex> запросов, следовательно
<tex> 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 </tex> <tex> (\ast) </tex>
Для удобства введем обозначения:
# Весом узла с ключом <tex> q </tex> будем называть величину <tex> w(q) =\displaystyle \frac {1}{\left(\lvert q - f \rvert + 1 \right )^{2}} </tex>.
# Размером узла, содержащего ключ <tex> q </tex>, будем называть величину <tex> s(q) = \displaystyle \sum_{y} w(y) </tex>, где <tex> y </tex> {{---}} узлы поддерева с корнем в <tex> q </tex>.
# <tex> r(q) = \log_{2}s(q) </tex> {{---}} ранг узла.
# Потенциал дерева обозначим как <tex> \Phi = \displaystyle \sum_{q=1}^{n} r(q) = \displaystyle \sum_{q=1}^{n} \log_{2}s(q) </tex>.
Пусть <tex> W </tex> {{---}} вес дерева. Тогда <tex> 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) </tex>.
Из определения размера узла следует, что <tex> w(q) \leqslant s(q) \leqslant W </tex>.
Также заметим, что для любого <tex> q </tex> от <tex> 1 </tex> до <tex> n </tex> верно <tex> w(q) \geqslant \displaystyle \frac {1}{n^{2}} </tex>.
Тогда изменение потенциала
<tex> \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) = </tex> <tex> \displaystyle O\Biggl(2 \cdot\sum_{q=1}^{n} \log_{2} n\Biggr) = O\left(n \log_{2}n\right) </tex>.
Обозначим за <tex> t </tex> корень сплей-дерева. Тогда, воспользовавшись вышеуказанной леммой, получаем, что
<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 - f \rvert + 1 \right)^{2} \right ) \right ) + 1 = O\left(\log_{2} \left(\lvert q - f \rvert + 1 \right) \right ) + 1 </tex>
Тогда, подставляя найденные значения в формулу <tex> (\ast) </tex>, получаем, что
<tex>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) = </tex> <tex> \displaystyle O \left (n \log_{2} n + m + \displaystyle \sum_{i=1}^{m} \log_2 \left( \lvert q_{i} - f \rvert + 1 \right) \right)</tex>
}}
|id = Th1
|about =
о близких запросах в сплей-дереве
|statement =
Пусть в сплей-дерево сложены ключи <tex> 1, \dotsc, n </tex>, зафиксируем один из ключей <tex> f </tex>, пусть выполняется <tex> m </tex> запросов к ключам. Тогда суммарное время на запросы есть <tex> \displaystyle O(n \log_{2} n + m + \sum_{i=1}^{m} \log_2 ( \lvert q_{i} - f \rvert + 1)) </tex>, где <tex> q_{i} </tex> {{---}} <tex> i </tex>-й запрос.
|proof =
Для доказательства теоремы воспользуемся методом потенциалов:
<tex> a_{i} = t_{i} + \Phi_{i} - \Phi_{i-1} </tex>
По условию выполняется <tex> m </tex> запросов, следовательно
<tex> 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 </tex> <tex> (\ast) </tex>
Для удобства введем обозначения:
# Весом узла с ключом <tex> q </tex> будем называть величину <tex> w(q) =\displaystyle \frac {1}{\left(\lvert q - f \rvert + 1 \right )^{2}} </tex>.
# Размером узла, содержащего ключ <tex> q </tex>, будем называть величину <tex> s(q) = \displaystyle \sum_{y} w(y) </tex>, где <tex> y </tex> {{---}} узлы поддерева с корнем в <tex> q </tex>.
# <tex> r(q) = \log_{2}s(q) </tex> {{---}} ранг узла.
# Потенциал дерева обозначим как <tex> \Phi = \displaystyle \sum_{q=1}^{n} r(q) = \displaystyle \sum_{q=1}^{n} \log_{2}s(q) </tex>.
Пусть <tex> W </tex> {{---}} вес дерева. Тогда <tex> 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) </tex>.
Из определения размера узла следует, что <tex> w(q) \leqslant s(q) \leqslant W </tex>.
Также заметим, что для любого <tex> q </tex> от <tex> 1 </tex> до <tex> n </tex> верно <tex> w(q) \geqslant \displaystyle \frac {1}{n^{2}} </tex>.
Тогда изменение потенциала
<tex> \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) = </tex> <tex> \displaystyle O\Biggl(2 \cdot\sum_{q=1}^{n} \log_{2} n\Biggr) = O\left(n \log_{2}n\right) </tex>.
Обозначим за <tex> t </tex> корень сплей-дерева. Тогда, воспользовавшись вышеуказанной леммой, получаем, что
<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 - f \rvert + 1 \right)^{2} \right ) \right ) + 1 = O\left(\log_{2} \left(\lvert q - f \rvert + 1 \right) \right ) + 1 </tex>
Тогда, подставляя найденные значения в формулу <tex> (\ast) </tex>, получаем, что
<tex>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) = </tex> <tex> \displaystyle O \left (n \log_{2} n + m + \displaystyle \sum_{i=1}^{m} \log_2 \left( \lvert q_{i} - f \rvert + 1 \right) \right)</tex>
}}
