|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 03 Mar 2003 14:14:42
To : Nick Kovaliov
Subject : Re: как их усреднять?
--------------------------------------------------------------------------------
Mon Mar 03 2003 12:05, Nick Kovaliov wrote to Evgenij Masherov:
NK> О !!!
NK> А если сделать две двоичных кучи -
NK> одна те, которые меньше медианы,
NK> вторая, которые больше ...
NK> Hу всё, решили проблему :))
NK> Итак -
NK> ----
NK> У нас уже есть эти две кучи
NK> (H_less, H_bigger) и медиана.
NK> Появляется новый эл-т -
NK> посмотреть, больше он медианы, или меньше.
NK> Если новый эл-т меньше медианы,
NK> то вставляем его в H_less,
NK> и извлекаем из H_less максимальный эл-т,
NK> таким образом, корректируем медиану
NK> В данном случае кол-во нечётное,
NK> значит медиана должна быть равна этому эл-ту.
NK> Если новый эл-т больше медианы,
NK> то вставляем его в H_bigger,
NK> и извлекаем из H_bigger минимальный эл-т,
NK> и корректируем медиану.
NK> ----
NK> Hу как ? ;-)
NK> Скорость гарантировано не хуже log2(N),
NK> и накладные расходы не большие
NK> по сравнению с копированием массива.
NK> Hа асме легко оптимиздится, если нада.
Hе решена задача... Hадо выбрасывать на каждом шаге не ближайший, а отстоящий
на 116 позиций от вновь поступившего.
Я бы делал с кольцевым буфером указателей на элементы отсортированного
массива, для отслеживания, что выбрасываем. Вставкой вновь поступившего на
место выброшенного и серией сдвигов до места. В худшем случае линейная
сложность, хотя, сделав поиск места делением пополам, ограничиваем линейную по
сложности часть только сдвигами (а вот тут можно и машиннозависимые приемчики
показать...) Впрочем, это близко к уже рассматривавшемуся.
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
