Обсуждение:Декартово дерево — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Приоритет: Новая тема)
 
(не показана 21 промежуточная версия 5 участников)
Строка 1: Строка 1:
TODO: запилить доказательство логарифмической оценки высоты дерева. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 10:34, 29 июня 2011 (UTC)
+
: {{tick | ticked=1}} зачем-то tree + heap написано в техе.
 +
:: По-моему, так лучше выглядит (мимокрокодил) [[Участник:SkudarnovYaroslav|SkudarnovYaroslav]] 19:52, 6 февраля 2012 (MSK)
 +
: {{tick | ticked=1}} Убрать «описание», запихать его в шапку статьи. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 14:04, 14 апреля 2012 (GST)
 +
:: либо везде используй <tex> X </tex>, либо везде <tex> x </tex>. Лучше маленькие буквы, имхо. Тут же написать, что x — ключ, а y — приоритет.
  
----
+
: {{tick | ticked=1}} Добавить интервики. Тут и бинарное дерево поиска, и куча, и на неявный ключ, и на случайную величину, и на линейность матожидания можно сослаться.
  
Понятие «ключ» и «приоритет» дается позже, чем используется. Плюс копи-паста с [http://e-maxx.ru/algo|емакса]. На мой взгляд, статью нужно подправить и немного дополнить псевдокодом. --[[Участник:GosuGDR|GosuGDR]] 07:43, 9 октября 2011 (UTC)
+
: {{tick | ticked=1}} написать, как строить декартово дерево за O(n), если заранее есть ключи в возрастающем порядке.
 +
:: {{tick | ticked=1}} Хорошо, что есть рекурсивный алгоритм, но про его асимптотику тожно можно что-нибудь написать. Хотя в нем вроде особого смысла нет,  так как он, кажется, может работать за столько же, как если бы мы тупо добавляли по одному элементу в дерево.
 +
::: Ну а h у нас может быть O(n). Напиши сразу, что O(n^2) и все.
 +
:: {{tick | ticked=1}} «делаем шаг по склону вверх» — ээ, какая-то упоротая фраза.
 +
 
 +
: {{tick | ticked=1}} вообще ничего нет про кприоритет, как он выбирается и все такое.
 +
: {{tick | ticked=1}} запилить доказательство логарифмической оценки высоты дерева.
 +
: {{tick | ticked=1}} операции лучше объединить в один раздел, а виды опреаций сделать подразделами
 +
: {{tick | ticked=1}} к split и merge неплохо бы небольшой псевдокод.
 +
:: Почитай правила оформления псевдокода.--[[Участник:Dgerasimov|Дмитрий Герасимов]] 16:50, 21 апреля 2012 (GST)
 +
 
 +
 
 +
: {{tick | ticked=1}} "Реализация №1:" -- зачем двоеточие в названии раздела?
 +
: {{tick | ticked=1}} Написать, чем отличаются реализации 1 и 2 друг от друга.
 +
:: '''Наверное, они отличаются не тем, что не используется merge или split, а в том, что просто их меньше во второй реализации?'''--[[Участник:Dgerasimov|Дмитрий Герасимов]] 16:40, 28 апреля 2012 (GST)
 +
::: Если написать что в реализации 2 используется меньше split или merge, будет выглядеть не очень, когда их там в принципе нет(Редактор)
 +
:::: Гм, ладно, сойдет. Кстати, можно подписываться с помощью <nowiki>--~~~~</nowiki>.
 +
:: И писать «этот вариант отличается» надо либо после объявления реализации № 2, либо вообще после неет.
 +
: {{tick | ticked=1}} А вообще почему-то реализация 1 расписана по пунктом, а во второй все сплошным текстом.
 +
: {{tick | ticked=1}} добавить категории --[[Участник:Dgerasimov|Дмитрий Герасимов]] 19:11, 6 февраля 2012 (MSK)
 +
: {{tick | ticked=1}} нет источников --[[Участник:Rybak|Андрей Рыбак]] 12:36, 25 марта 2012 (GST)
 +
 
 +
: {{tick | ticked=1}} доказательство:
 +
:: {{tick | ticked=1}}«являются незавимыми непрерывными случайными величинами с одинаковым вероятностным распределением» — непрерывные случайные величины? Гм, вроде этого не было в курсе дискретки, ну это еще интуитивно более-менее ясно. А вот что такое «одинаковое распределение»?
 +
::: «с одного и того же распределения» — бред. возьмем для приортиетов нечестную монету (или что-то подобное), она может давать независимые случайные величины, но для приоритетов не подходит.
 +
:::: Все еще не исправлено --[[Участник:Dgerasimov|Дмитрий Герасимов]] 11:44, 26 апреля 2012 (GST)<nowiki>Вставьте сюда текст, который не нужно форматировать</nowiki>
 +
::::: '''НЕ ИСПРАВЛЕНО!!!!!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)
 +
:::::::: Должны быть разными, в том числе. В общем, то, что тебе нужно называется равномерным распределением. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 23:06, 3 мая 2012 (GST)
 +
::::::::: Ну и где что-то про равномерное распределение? --[[Участник:Dgerasimov|Дмитрий Герасимов]] 16:19, 15 мая 2012 (GST)
 +
:: вот эта запись x_i — ancestor x_j — не очень. Во-первых, ancestor of, а во-вторых, «—» как-то неуместно. Лучше x_i is ancestor of x_j, в общем.
 +
:: «использовали линейность математического ожидания E» — эм, просто линейность математического ожидания, зачем значок E тут?
 +
:: В X_k,i у индексов тех поехал.
 +
:: «минимальный приоритет в treap’е» — в treap'е -> в декартовом дереве
 +
:: Как-то доказательство пошло сначала с индукционного перехода, а потом к базе. Надо бы наоборот.
 +
:: как-то ты сразу суммы свернул, надо чуть поподробнее расписать замены диапазонов суммирования, ну или что там используется.
 +
::: {{tick | ticked=1}} Только пояснение о том, какое неравенство использвуется, лучше в скобках после написать, а не с новой строки.
 +
:::: {{tick | ticked=1}} И обозначай в тех логарифм не как ln, а как \ln.
 +
::::: Ааа, хрень полная написана. Во-первых, log n и ln n при маленьких n отличаются так же, как при больших — а именно в константу раз. Во-вторых, значок ~ означает, что функции эквивалентны, то есть их частное при больших n стремится к 1.
 +
: {{tick | ticked=1}} Кстати, там где ты говоришь про высоту декартового дерева, говори не 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)
 +
 
 +
== Приоритет ==
 +
 
 +
Ребятушки, у вас полстатьи в корне максимальный проритет, полстатьи — минимальный. Давайте уж сойдемся на том, что приоритет, он на то и приоритет, чтобы первым шел тот, у кого он больше. [[Участник:Kirelagin|Кирилл Елагин]] 21:05, 28 января 2014 (GST)

Текущая версия на 20:05, 28 января 2014

зачем-то tree + heap написано в техе.
По-моему, так лучше выглядит (мимокрокодил) SkudarnovYaroslav 19:52, 6 февраля 2012 (MSK)
Убрать «описание», запихать его в шапку статьи. --Дмитрий Герасимов 14:04, 14 апреля 2012 (GST)
либо везде используй [math] X [/math], либо везде [math] x [/math]. Лучше маленькие буквы, имхо. Тут же написать, что x — ключ, а y — приоритет.
Добавить интервики. Тут и бинарное дерево поиска, и куча, и на неявный ключ, и на случайную величину, и на линейность матожидания можно сослаться.
написать, как строить декартово дерево за O(n), если заранее есть ключи в возрастающем порядке.
Хорошо, что есть рекурсивный алгоритм, но про его асимптотику тожно можно что-нибудь написать. Хотя в нем вроде особого смысла нет, так как он, кажется, может работать за столько же, как если бы мы тупо добавляли по одному элементу в дерево.
Ну а h у нас может быть O(n). Напиши сразу, что O(n^2) и все.
«делаем шаг по склону вверх» — ээ, какая-то упоротая фраза.
вообще ничего нет про кприоритет, как он выбирается и все такое.
запилить доказательство логарифмической оценки высоты дерева.
операции лучше объединить в один раздел, а виды опреаций сделать подразделами
к split и merge неплохо бы небольшой псевдокод.
Почитай правила оформления псевдокода.--Дмитрий Герасимов 16:50, 21 апреля 2012 (GST)


"Реализация №1:" -- зачем двоеточие в названии раздела?
Написать, чем отличаются реализации 1 и 2 друг от друга.
Наверное, они отличаются не тем, что не используется merge или split, а в том, что просто их меньше во второй реализации?--Дмитрий Герасимов 16:40, 28 апреля 2012 (GST)
Если написать что в реализации 2 используется меньше split или merge, будет выглядеть не очень, когда их там в принципе нет(Редактор)
Гм, ладно, сойдет. Кстати, можно подписываться с помощью --~~~~.
И писать «этот вариант отличается» надо либо после объявления реализации № 2, либо вообще после неет.
А вообще почему-то реализация 1 расписана по пунктом, а во второй все сплошным текстом.
добавить категории --Дмитрий Герасимов 19:11, 6 февраля 2012 (MSK)
нет источников --Андрей Рыбак 12:36, 25 марта 2012 (GST)
доказательство:
«являются незавимыми непрерывными случайными величинами с одинаковым вероятностным распределением» — непрерывные случайные величины? Гм, вроде этого не было в курсе дискретки, ну это еще интуитивно более-менее ясно. А вот что такое «одинаковое распределение»?
«с одного и того же распределения» — бред. возьмем для приортиетов нечестную монету (или что-то подобное), она может давать независимые случайные величины, но для приоритетов не подходит.
Все еще не исправлено --Дмитрий Герасимов 11:44, 26 апреля 2012 (GST)Вставьте сюда текст, который не нужно форматировать
НЕ ИСПРАВЛЕНО!!!!!1111 --Дмитрий Герасимов 16:40, 28 апреля 2012 (GST)
ох. Суть формулировки ты не изменил, а только сделал более мутной. «приоритеты которого выбраны случайно и независимо». Возьмем _нечестную_ игральную кость с 1000000000 граней, к примеру, будем выбирать ею приоритеты. Случайно? Случайно. Независимо? Независимо. Подходит для выбора приоритетов? Нет. В чем же проблема?--Дмитрий Герасимов 13:48, 1 мая 2012 (GST)
Мне кажется, что все предыдущие формулировки были мутными, ведь нам нужно чтобы высота была логарифм, поэтому выбираем приоритеты случайно, единственное что надо выделить это независимость, она используется в утверждении что среди X_{i,k} любая вершина может оказаться с минимальным приоритетом. Иначе говоря я не вижу мест, где моей формулировки недостаточно. Насчет проблемы, если она заключается в том что приоритеты должны быть разными, то да формулировка не до конца корректна. Но если к примеру написать как написано где то глубоко в кормене "Декартово дерево из n ключей, приоритеты 'y' у которого выбраны так, что n! перестановок входных ключей равновероятны, имеет высоту O(log n)" станет несколько ... в общем я написал в шапке доказательства -- Орынбаев Хусаин 15:58, 1 мая 2012 (GST)
Должны быть разными, в том числе. В общем, то, что тебе нужно называется равномерным распределением. --Дмитрий Герасимов 23:06, 3 мая 2012 (GST)
Ну и где что-то про равномерное распределение? --Дмитрий Герасимов 16:19, 15 мая 2012 (GST)
вот эта запись x_i — ancestor x_j — не очень. Во-первых, ancestor of, а во-вторых, «—» как-то неуместно. Лучше x_i is ancestor of x_j, в общем.
«использовали линейность математического ожидания E» — эм, просто линейность математического ожидания, зачем значок E тут?
В X_k,i у индексов тех поехал.
«минимальный приоритет в treap’е» — в treap'е -> в декартовом дереве
Как-то доказательство пошло сначала с индукционного перехода, а потом к базе. Надо бы наоборот.
как-то ты сразу суммы свернул, надо чуть поподробнее расписать замены диапазонов суммирования, ну или что там используется.
Только пояснение о том, какое неравенство использвуется, лучше в скобках после написать, а не с новой строки.
И обозначай в тех логарифм не как ln, а как \ln.
Ааа, хрень полная написана. Во-первых, log n и ln n при маленьких n отличаются так же, как при больших — а именно в константу раз. Во-вторых, значок ~ означает, что функции эквивалентны, то есть их частное при больших n стремится к 1.
Кстати, там где ты говоришь про высоту декартового дерева, говори не O(\ln n), а O(\log n) (просто один раз упомяни, что они в константу раз различаются и все).
У тебя merge в техе в разных местах по-разному написан, то [math] Merge [/math], то [math]\operatorname{Merge}[/math].
«Построение декартово дерева»
все еще не исправлено...--Дмитрий Герасимов 16:40, 28 апреля 2012 (GST)
аргх. правильно говорить «декартова дерева». --Дмитрий Герасимов 13:48, 1 мая 2012 (GST)

Приоритет

Ребятушки, у вас полстатьи в корне максимальный проритет, полстатьи — минимальный. Давайте уж сойдемся на том, что приоритет, он на то и приоритет, чтобы первым шел тот, у кого он больше. Кирилл Елагин 21:05, 28 января 2014 (GST)