Изменения

Перейти к: навигация, поиск

Обсуждение:Декартово дерево

14 байт добавлено, 16:02, 1 мая 2012
Нет описания правки
::::: '''НЕ ИСПРАВЛЕНО!!!!!1111''' --[[Участник:Dgerasimov|Дмитрий Герасимов]] 16:40, 28 апреля 2012 (GST)
:::::: ох. Суть формулировки ты не изменил, а только сделал более мутной. «приоритеты которого выбраны случайно и независимо». Возьмем _нечестную_ игральную кость с 1000000000 граней, к примеру, будем выбирать ею приоритеты. Случайно? Случайно. Независимо? Независимо. Подходит для выбора приоритетов? Нет. В чем же проблема?--[[Участник:Dgerasimov|Дмитрий Герасимов]] 13:48, 1 мая 2012 (GST)
::::::: Мне кажется, что все предыдущие формулировки были мутными, ведь нам нужно чтобы высота была логарифм, поэтому выбираем приоритеты случайно, единственное что надо выделить это независимость, она используется в утверждении что среди X_{i,k} любая вершина может оказаться с минимальным приоритетом. Иначе говоря я не вижу мест, где моей формулировки недостаточно. Насчет проблемы, если она заключается в том что приоритеты должны быть разными, то да формулировка не до конца корректна. Но если к примеру написать как написано где то глубоко в кормене "Декартово дерево из n ключей, приоритеты 'y' у которого выбраны так, что n! перестановок входных ключей равновероятны, имеет высоту O(log n)" станет несколько ... в общем я написал в шапке раздела доказательства -- [[Участник:Орынбаев Хусаин|Орынбаев Хусаин]] 15:58, 1 мая 2012 (GST)
:: вот эта запись x_i — ancestor x_j — не очень. Во-первых, ancestor of, а во-вторых, «—» как-то неуместно. Лучше x_i is ancestor of x_j, в общем.
:: «использовали линейность математического ожидания E» — эм, просто линейность математического ожидания, зачем значок E тут?

Навигация