166
правок
Изменения
→Высота в декартовом дереве с случайными приоритетами
== Высота в декартовом дереве с случайными приоритетами ==
{{Теорема
|statement = Декартово дерево из <tex>n</tex> узлов, приоритеты <tex>y</tex> которого выбраны случайно и независимо, имеет высоту <tex>O(\ln log n)</tex>.
|proof=
Подставив последнее в нашу формулу с математическим ожиданием получим:
: <tex>E(d(x_k)) = \sum\limits_{i = 1}^{n} Pr[A_{i,k} = 1] = \sum\limits_{i = 1}^{k - 1} \frac{1}{k - i + 1} + \sum\limits_{i = k + 1}^{n} \frac{1}{i - k + 1} \le \ln(k) + \ln(n-k) + 2</tex> (здесь мы использовали неравенство <tex>\sum\limits_{i = 1}^{n} \frac{1}{i} \le \ln(n) + 1</tex>)
: также известно, что <tex>\log(n) \sim \ln(n)</tex>, поэтому <tex>\log(n) = O(\ln(n))</tex>.
В итоге мы получили что <tex>E(d(x_k)) = O(\lnlog(n))</tex>.
}}
