Обсуждение:Декартово дерево — различия между версиями
Rybak (обсуждение | вклад) |
|||
| Строка 1: | Строка 1: | ||
| − | : {{tick}} зачем-то tree + heap написано в техе. | + | : {{tick | ticked=1}} зачем-то tree + heap написано в техе. |
:: По-моему, так лучше выглядит (мимокрокодил) [[Участник:SkudarnovYaroslav|SkudarnovYaroslav]] 19:52, 6 февраля 2012 (MSK) | :: По-моему, так лучше выглядит (мимокрокодил) [[Участник:SkudarnovYaroslav|SkudarnovYaroslav]] 19:52, 6 февраля 2012 (MSK) | ||
| − | : {{tick}} вообще ничего нет про кприоритет, как он выбирается и все такое. | + | : {{tick}} Убрать «описание», запихать его в шапку статьи. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 14:04, 14 апреля 2012 (GST) |
| + | :: либо везде используй <tex> X </tex>, либо везде <tex> x </tex>. Лучше маленькие буквы, имхо. Тут же написать, что x — ключ, а y — приоритет. | ||
| + | |||
| + | : {{tick}} Добавить интервики. Тут и бинарное дерево поиска, и куча, и на неявный ключ, и на случайную величину, и на линейность матожидания можно сослаться. | ||
| + | |||
| + | : {{tick}} написать, как строить декартово дерево за O(n), если заранее есть ключи в возрастающем порядке. | ||
| + | |||
| + | : {{tick | ticked=1}} вообще ничего нет про кприоритет, как он выбирается и все такое. | ||
: {{tick}} запилить доказательство логарифмической оценки высоты дерева. | : {{tick}} запилить доказательство логарифмической оценки высоты дерева. | ||
| − | : {{tick}} операции лучше объединить в один раздел, а виды опреаций сделать подразделами | + | : {{tick | ticked=1}} операции лучше объединить в один раздел, а виды опреаций сделать подразделами |
| − | : {{tick}} "Реализация №1:" -- зачем двоеточие в названии раздела? | + | : {{tick}} к split и merge неплохо бы небольшой псевдокод. |
| − | : {{tick}} Написать, чем отличаются реализации 1 и 2 друг от друга. А вообще почему-то реализация 1 расписана по пунктом, а во второй все сплошным текстом. | + | |
| − | : {{tick}} добавить категории --[[Участник:Dgerasimov|Дмитрий Герасимов]] 19:11, 6 февраля 2012 (MSK) | + | : {{tick | ticked=1}} "Реализация №1:" -- зачем двоеточие в названии раздела? |
| − | : {{tick}} нет источников --[[Участник:Rybak|Андрей Рыбак]] 12:36, 25 марта 2012 (GST) | + | : {{tick}} Написать, чем отличаются реализации 1 и 2 друг от друга. |
| + | : {{tick | ticked=1}} А вообще почему-то реализация 1 расписана по пунктом, а во второй все сплошным текстом. | ||
| + | : {{tick | ticked=1}} добавить категории --[[Участник:Dgerasimov|Дмитрий Герасимов]] 19:11, 6 февраля 2012 (MSK) | ||
| + | : {{tick | ticked=1}} нет источников --[[Участник:Rybak|Андрей Рыбак]] 12:36, 25 марта 2012 (GST) | ||
| + | |||
| + | : {{tick}} доказательство: | ||
| + | :: «являются незавимыми непрерывными случайными величинами с одинаковым вероятностным распределением» — непрерывные случайные величины? Гм, вроде этого не было в курсе дискретки, ну это еще интуитивно более-менее ясно. А вот что такое «одинаковое распределение»? | ||
| + | :: вот эта запись x_i — ancestor x_j — не очень. Во-первых, ancestor of, а во-вторых, «—» как-то неуместно. Лучше x_i is ancestor of x_j, в общем. | ||
| + | :: «использовали линейность математического ожидания E» — эм, просто линейность математического ожидания, зачем значок E тут? | ||
| + | :: В X_k,i у индексов тех поехал. | ||
| + | :: «минимальный приоритет в treap’е» — в treap'е -> в декартовом дереве | ||
| + | :: Как-то доказательство пошло сначала с индукционного перехода, а потом к базе. Надо бы наоборот. | ||
| + | :: как-то ты сразу суммы свернул, надо чуть поподробнее расписать замены диапазонов суммирования, ну или что там используется. | ||
Версия 13:04, 14 апреля 2012
- ☑ зачем-то tree + heap написано в техе.
- По-моему, так лучше выглядит (мимокрокодил) SkudarnovYaroslav 19:52, 6 февраля 2012 (MSK)
- ☐ Убрать «описание», запихать его в шапку статьи. --Дмитрий Герасимов 14:04, 14 апреля 2012 (GST)
- либо везде используй , либо везде . Лучше маленькие буквы, имхо. Тут же написать, что x — ключ, а y — приоритет.
- ☐ Добавить интервики. Тут и бинарное дерево поиска, и куча, и на неявный ключ, и на случайную величину, и на линейность матожидания можно сослаться.
- ☐ написать, как строить декартово дерево за O(n), если заранее есть ключи в возрастающем порядке.
- ☑ вообще ничего нет про кприоритет, как он выбирается и все такое.
- ☐ запилить доказательство логарифмической оценки высоты дерева.
- ☑ операции лучше объединить в один раздел, а виды опреаций сделать подразделами
- ☐ к split и merge неплохо бы небольшой псевдокод.
- ☑ "Реализация №1:" -- зачем двоеточие в названии раздела?
- ☐ Написать, чем отличаются реализации 1 и 2 друг от друга.
- ☑ А вообще почему-то реализация 1 расписана по пунктом, а во второй все сплошным текстом.
- ☑ добавить категории --Дмитрий Герасимов 19:11, 6 февраля 2012 (MSK)
- ☑ нет источников --Андрей Рыбак 12:36, 25 марта 2012 (GST)
- ☐ доказательство:
- «являются незавимыми непрерывными случайными величинами с одинаковым вероятностным распределением» — непрерывные случайные величины? Гм, вроде этого не было в курсе дискретки, ну это еще интуитивно более-менее ясно. А вот что такое «одинаковое распределение»?
- вот эта запись x_i — ancestor x_j — не очень. Во-первых, ancestor of, а во-вторых, «—» как-то неуместно. Лучше x_i is ancestor of x_j, в общем.
- «использовали линейность математического ожидания E» — эм, просто линейность математического ожидания, зачем значок E тут?
- В X_k,i у индексов тех поехал.
- «минимальный приоритет в treap’е» — в treap'е -> в декартовом дереве
- Как-то доказательство пошло сначала с индукционного перехода, а потом к базе. Надо бы наоборот.
- как-то ты сразу суммы свернул, надо чуть поподробнее расписать замены диапазонов суммирования, ну или что там используется.
