Обсуждение:Декартово дерево — различия между версиями
| Строка 7: | Строка 7: | ||
: {{tick | ticked=1}} написать, как строить декартово дерево за O(n), если заранее есть ключи в возрастающем порядке. | : {{tick | ticked=1}} написать, как строить декартово дерево за O(n), если заранее есть ключи в возрастающем порядке. | ||
| − | :: {{tick}} Хорошо, что есть рекурсивный алгоритм, но про его асимптотику тожно можно что-нибудь написать. Хотя в нем вроде особого смысла нет, так как он, кажется, может работать за столько же, как если бы мы тупо добавляли по одному элементу в дерево. | + | :: {{tick | ticked=1}} Хорошо, что есть рекурсивный алгоритм, но про его асимптотику тожно можно что-нибудь написать. Хотя в нем вроде особого смысла нет, так как он, кажется, может работать за столько же, как если бы мы тупо добавляли по одному элементу в дерево. |
::: Ну а h у нас может быть O(n). Напиши сразу, что O(n^2) и все. | ::: Ну а h у нас может быть O(n). Напиши сразу, что O(n^2) и все. | ||
:: {{tick | ticked=1}} «делаем шаг по склону вверх» — ээ, какая-то упоротая фраза. | :: {{tick | ticked=1}} «делаем шаг по склону вверх» — ээ, какая-то упоротая фраза. | ||
| Строка 14: | Строка 14: | ||
: {{tick | ticked=1}} запилить доказательство логарифмической оценки высоты дерева. | : {{tick | ticked=1}} запилить доказательство логарифмической оценки высоты дерева. | ||
: {{tick | ticked=1}} операции лучше объединить в один раздел, а виды опреаций сделать подразделами | : {{tick | ticked=1}} операции лучше объединить в один раздел, а виды опреаций сделать подразделами | ||
| − | : {{tick}} к split и merge неплохо бы небольшой псевдокод. | + | : {{tick | ticked=1}} к split и merge неплохо бы небольшой псевдокод. |
:: Почитай правила оформления псевдокода.--[[Участник:Dgerasimov|Дмитрий Герасимов]] 16:50, 21 апреля 2012 (GST) | :: Почитай правила оформления псевдокода.--[[Участник:Dgerasimov|Дмитрий Герасимов]] 16:50, 21 апреля 2012 (GST) | ||
| Строка 20: | Строка 20: | ||
: {{tick | ticked=1}} "Реализация №1:" -- зачем двоеточие в названии раздела? | : {{tick | ticked=1}} "Реализация №1:" -- зачем двоеточие в названии раздела? | ||
: {{tick}} Написать, чем отличаются реализации 1 и 2 друг от друга. | : {{tick}} Написать, чем отличаются реализации 1 и 2 друг от друга. | ||
| − | :: Наверное, они отличаются не тем, что не используется merge или split, а в том, что просто их меньше во второй реализации?--[[Участник:Dgerasimov|Дмитрий Герасимов]] 16: | + | :: '''Наверное, они отличаются не тем, что не используется merge или split, а в том, что просто их меньше во второй реализации?'''--[[Участник:Dgerasimov|Дмитрий Герасимов]] 16:40, 28 апреля 2012 (GST) |
:: И писать «этот вариант отличается» надо либо после объявления реализации № 2, либо вообще после неет. | :: И писать «этот вариант отличается» надо либо после объявления реализации № 2, либо вообще после неет. | ||
: {{tick | ticked=1}} А вообще почему-то реализация 1 расписана по пунктом, а во второй все сплошным текстом. | : {{tick | ticked=1}} А вообще почему-то реализация 1 расписана по пунктом, а во второй все сплошным текстом. | ||
| Строка 30: | Строка 30: | ||
::: «с одного и того же распределения» — бред. возьмем для приортиетов нечестную монету (или что-то подобное), она может давать независимые случайные величины, но для приоритетов не подходит. | ::: «с одного и того же распределения» — бред. возьмем для приортиетов нечестную монету (или что-то подобное), она может давать независимые случайные величины, но для приоритетов не подходит. | ||
:::: Все еще не исправлено --[[Участник:Dgerasimov|Дмитрий Герасимов]] 11:44, 26 апреля 2012 (GST)<nowiki>Вставьте сюда текст, который не нужно форматировать</nowiki> | :::: Все еще не исправлено --[[Участник:Dgerasimov|Дмитрий Герасимов]] 11:44, 26 апреля 2012 (GST)<nowiki>Вставьте сюда текст, который не нужно форматировать</nowiki> | ||
| + | ::::: '''НЕ ИСПРАВЛЕНО!!!!!1111''' --[[Участник:Dgerasimov|Дмитрий Герасимов]] 16:40, 28 апреля 2012 (GST) | ||
:: вот эта запись x_i — ancestor x_j — не очень. Во-первых, ancestor of, а во-вторых, «—» как-то неуместно. Лучше x_i is ancestor of x_j, в общем. | :: вот эта запись x_i — ancestor x_j — не очень. Во-первых, ancestor of, а во-вторых, «—» как-то неуместно. Лучше x_i is ancestor of x_j, в общем. | ||
:: «использовали линейность математического ожидания E» — эм, просто линейность математического ожидания, зачем значок E тут? | :: «использовали линейность математического ожидания E» — эм, просто линейность математического ожидания, зачем значок E тут? | ||
| Строка 41: | Строка 42: | ||
: {{tick | ticked=1}} У тебя merge в техе в разных местах по-разному написан, то <tex> Merge </tex>, то <tex>\operatorname{Merge}</tex>. | : {{tick | ticked=1}} У тебя merge в техе в разных местах по-разному написан, то <tex> Merge </tex>, то <tex>\operatorname{Merge}</tex>. | ||
: {{tick}} «Построение декартово дерева» | : {{tick}} «Построение декартово дерева» | ||
| + | :: все еще не исправлено...--[[Участник:Dgerasimov|Дмитрий Герасимов]] 16:40, 28 апреля 2012 (GST) | ||
Версия 15:40, 28 апреля 2012
- ☑ зачем-то tree + heap написано в техе.
- По-моему, так лучше выглядит (мимокрокодил) SkudarnovYaroslav 19:52, 6 февраля 2012 (MSK)
- ☑ Убрать «описание», запихать его в шапку статьи. --Дмитрий Герасимов 14:04, 14 апреля 2012 (GST)
- либо везде используй , либо везде . Лучше маленькие буквы, имхо. Тут же написать, что 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, либо вообще после неет.
- ☑ А вообще почему-то реализация 1 расписана по пунктом, а во второй все сплошным текстом.
- ☑ добавить категории --Дмитрий Герасимов 19:11, 6 февраля 2012 (MSK)
- ☑ нет источников --Андрей Рыбак 12:36, 25 марта 2012 (GST)
- ☐ доказательство:
- ☐«являются незавимыми непрерывными случайными величинами с одинаковым вероятностным распределением» — непрерывные случайные величины? Гм, вроде этого не было в курсе дискретки, ну это еще интуитивно более-менее ясно. А вот что такое «одинаковое распределение»?
- «с одного и того же распределения» — бред. возьмем для приортиетов нечестную монету (или что-то подобное), она может давать независимые случайные величины, но для приоритетов не подходит.
- Все еще не исправлено --Дмитрий Герасимов 11:44, 26 апреля 2012 (GST)Вставьте сюда текст, который не нужно форматировать
- НЕ ИСПРАВЛЕНО!!!!!1111 --Дмитрий Герасимов 16:40, 28 апреля 2012 (GST)
- Все еще не исправлено --Дмитрий Герасимов 11:44, 26 апреля 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.
- ☑ Только пояснение о том, какое неравенство использвуется, лучше в скобках после написать, а не с новой строки.
- ☐«являются незавимыми непрерывными случайными величинами с одинаковым вероятностным распределением» — непрерывные случайные величины? Гм, вроде этого не было в курсе дискретки, ну это еще интуитивно более-менее ясно. А вот что такое «одинаковое распределение»?
- ☑ У тебя merge в техе в разных местах по-разному написан, то , то .
- ☐ «Построение декартово дерева»
- все еще не исправлено...--Дмитрий Герасимов 16:40, 28 апреля 2012 (GST)
