172
правки
Изменения
→Высота в декартовом дереве с случайными приоритетами
Так как распределение приоритетов равномерное, каждая вершина среди <tex>X_{i, k}</tex> может иметь максимальный приоритет, мы немедленно приходим к следующему равенству:
: <tex>Pr[A_{i, j} = 1] = \left\{\begin{array}{lllc} \fracdfrac{1}{k - i + 1} &&, k \ > \ i\\
0 &&, k\ =\ i\\
\fracdfrac{1}{i - k + 1} &&, k \ < \ i\\
\end{array}\right.
</tex>
Подставив последнее в нашу формулу с математическим ожиданием получим:
: <tex>E(d(x_k)) = \sum\limits_{i = 1}^{n} Pr[A_{i,k} = 1] = \sum\limits_{i = 1}^{k - 1} \fracdfrac{1}{k - i + 1} + \sum\limits_{i = k + 1}^{n} \fracdfrac{1}{i - k + 1} \le \ln(k) + \ln(n-k) + 2</tex> (здесь мы использовали неравенство <tex>\sum\limits_{i = 1}^{n} \fracdfrac{1}{i} \le \ln(n) + 1</tex>)
: <tex>\log(n)</tex> отличается от <tex>\ln(n)</tex> в константу раз, поэтому <tex>\log(n) = O(\ln(n))</tex>.
