|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Nick Kovaliov 2:5020/400 03 Mar 2003 13:05:22
To : Evgenij Masherov
Subject : Re: как их усреднять?
--------------------------------------------------------------------------------
EM> Медиана в отсортированном ищется за О(1) :))
EM> (Смайлик потому, что просто за 1 операцию).
:)
EM> Или речь идет о поиске для выбрасывания ?
Да.
Ему нужно считать медиану по ходу поступления данных.
То есть медиану от последних 115 отсчётов.
EM> Да, видимо так. Логарифмика.
EM> Причем если первый шаг сделать
EM> не деление пополам а, скажем,
EM> на три или четыре части, учитывая,
EM> что предыдущая медиана почти точно посредине...
А какое имеет значение предыдущая медиана ?
Следующее значение ты не предскажешь,
а вставить в массив (или дерево) нужно именно его.
Задача определить, будет ли новое значение
справа, или слева от предыдущей медианы ...
Hо вставлять всё равно придётся в сортированое.
О !!!
А если сделать две двоичных кучи -
одна те, которые меньше медианы,
вторая, которые больше ...
Hу всё, решили проблему :))
Итак -
----
У нас уже есть эти две кучи
(H_less, H_bigger) и медиана.
Появляется новый эл-т -
посмотреть, больше он медианы, или меньше.
Если новый эл-т меньше медианы,
то вставляем его в H_less,
и извлекаем из H_less максимальный эл-т,
таким образом, корректируем медиану
В данном случае кол-во нечётное,
значит медиана должна быть равна этому эл-ту.
Если новый эл-т больше медианы,
то вставляем его в H_bigger,
и извлекаем из H_bigger минимальный эл-т,
и корректируем медиану.
----
Hу как ? ;-)
Скорость гарантировано не хуже log2(N),
и накладные расходы не большие
по сравнению с копированием массива.
Hа асме легко оптимиздится, если нада.
До встречи, всего наилучшего !
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
