1679
правок
Изменения
Нет описания правки
: {{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}} к split и merge неплохо бы небольшой псевдокод.
:: Почитай правила оформления псевдокода.--[[Участник:Dgerasimov|Дмитрий Герасимов]] 16:50, 21 апреля 2012 (GST)
: {{tick | ticked=1}} "Реализация №1:" -- зачем двоеточие в названии раздела?
: {{tick}} Написать, чем отличаются реализации 1 и 2 друг от друга.
:: '''Наверное, они отличаются не тем, что не используется merge или split, а в том, что просто их меньше во второй реализации?'''--[[Участник:Dgerasimov|Дмитрий Герасимов]] 16:5040, 21 28 апреля 2012 (GST)
:: И писать «этот вариант отличается» надо либо после объявления реализации № 2, либо вообще после неет.
: {{tick | ticked=1}} А вообще почему-то реализация 1 расписана по пунктом, а во второй все сплошным текстом.
::: «с одного и того же распределения» — бред. возьмем для приортиетов нечестную монету (или что-то подобное), она может давать независимые случайные величины, но для приоритетов не подходит.
:::: Все еще не исправлено --[[Участник: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, в общем.
:: «использовали линейность математического ожидания E» — эм, просто линейность математического ожидания, зачем значок E тут?
: {{tick | ticked=1}} У тебя merge в техе в разных местах по-разному написан, то <tex> Merge </tex>, то <tex>\operatorname{Merge}</tex>.
: {{tick}} «Построение декартово дерева»
:: все еще не исправлено...--[[Участник:Dgerasimov|Дмитрий Герасимов]] 16:40, 28 апреля 2012 (GST)
