1679
правок
Изменения
Нет описания правки
:::::: ох. Суть формулировки ты не изменил, а только сделал более мутной. «приоритеты которого выбраны случайно и независимо». Возьмем _нечестную_ игральную кость с 1000000000 граней, к примеру, будем выбирать ею приоритеты. Случайно? Случайно. Независимо? Независимо. Подходит для выбора приоритетов? Нет. В чем же проблема?--[[Участник:Dgerasimov|Дмитрий Герасимов]] 13:48, 1 мая 2012 (GST)
::::::: Мне кажется, что все предыдущие формулировки были мутными, ведь нам нужно чтобы высота была логарифм, поэтому выбираем приоритеты случайно, единственное что надо выделить это независимость, она используется в утверждении что среди X_{i,k} любая вершина может оказаться с минимальным приоритетом. Иначе говоря я не вижу мест, где моей формулировки недостаточно. Насчет проблемы, если она заключается в том что приоритеты должны быть разными, то да формулировка не до конца корректна. Но если к примеру написать как написано где то глубоко в кормене "Декартово дерево из n ключей, приоритеты 'y' у которого выбраны так, что n! перестановок входных ключей равновероятны, имеет высоту O(log n)" станет несколько ... в общем я написал в шапке доказательства -- [[Участник:Орынбаев Хусаин|Орынбаев Хусаин]] 15:58, 1 мая 2012 (GST)
:::::::: Должны быть разными, в том числе. В общем, то, что тебе нужно называется равномерным распределением. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 23:06, 3 мая 2012 (GST)
:: вот эта запись x_i — ancestor x_j — не очень. Во-первых, ancestor of, а во-вторых, «—» как-то неуместно. Лучше x_i is ancestor of x_j, в общем.
:: «использовали линейность математического ожидания E» — эм, просто линейность математического ожидания, зачем значок E тут?
:: как-то ты сразу суммы свернул, надо чуть поподробнее расписать замены диапазонов суммирования, ну или что там используется.
::: {{tick | ticked=1}} Только пояснение о том, какое неравенство использвуется, лучше в скобках после написать, а не с новой строки.
:::: {{tick}} И обозначай в тех логарифм не как ln, а как \ln.::::: Ааа, хрень полная написана. Во-первых, log n и ln n при маленьких n отличаются так же, как при больших — а именно в константу раз. Во-вторых, значок ~ означает, что функции эквивалентны, то есть их частное при больших n стремится к 1.
: {{tick}} Кстати, там где ты говоришь про высоту декартового дерева, говори не O(\ln n), а O(\log n) (просто один раз упомяни, что они в константу раз различаются и все).
: {{tick | ticked=1}} У тебя merge в техе в разных местах по-разному написан, то <tex> Merge </tex>, то <tex>\operatorname{Merge}</tex>.
: {{tick| ticked=1}} «Построение декартово дерева»
:: все еще не исправлено...--[[Участник:Dgerasimov|Дмитрий Герасимов]] 16:40, 28 апреля 2012 (GST)
::: аргх. правильно говорить «декартова дерева». --[[Участник:Dgerasimov|Дмитрий Герасимов]] 13:48, 1 мая 2012 (GST)
