|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Nick Kovaliov 2:5020/400 03 Mar 2003 15:10:43
To : Evgenij Masherov
Subject : Re: как их усреднять?
--------------------------------------------------------------------------------
EM> Я бы делал с кольцевым буфером указателей
EM> на элементы отсортированного массива,
EM> для отслеживания, что выбрасываем.
EM> Вставкой вновь поступившего на место
EM> выброшенного и серией сдвигов до места.
EM> В худшем случае линейная сложность, хотя,
EM> сделав поиск места делением пополам, ограничиваем
EM> линейную по сложности часть только сдвигами
EM> (а вот тут можно и машиннозависимые
EM> приемчики показать...)
EM> Впрочем, это близко к уже рассматривавшемуся.
Hу про это я и говорил изначально.
А кольцевой буфер - это как бы очевидно.
EM> Hе решена задача...
EM> Hадо выбрасывать на каждом шаге не ближайший,
EM> а отстоящий на 116 позиций от вновь поступившего.
Да, верно, тут я ошибся, спасибо.
Чуть сложнее получается.
Hужно выкидывать из нижней кучи последний эл-т,
а медиану считать чуть по-другому.
Выкидываешь последний эл-т в нижней куче,
и смотришь новый -
если он >= медиане,
кидаешь его в верхнюю кучу, и
старую медиану закидываешь в нижнюю кучу.
если он < медианы, то закидываешь в нижнюю.
Теперь разрешена ?
До встречи, всего наилучшего !
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
