|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 01 Mar 2003 10:18:24
To : Zahar Kiselev
Subject : как их усреднять?
--------------------------------------------------------------------------------
Fri Feb 28 2003 20:33, Zahar Kiselev wrote to Evgenij Masherov:
EM>> Примером метода второй группы является замена среднего
EM>> арифметического
EM>> медианой - значением, находящимся посредине упорядоченной по величине
EM>> выборки
ZK> Спасибо, это в точности то, что мне нужно.
ZK> Осталось придумать алгоритм, позволяющий делать такую выборку в виде
ZK> "скользящего окна" по последовательности отсчетов.
Первые N сортируем, медиана посредине. Запоминаем позиции элементов в
исходном сигнале. При сдвиге выбрасываем ушедший из выборки элемент (сложность
O(N)) и добавляем новый (сложность O(N)) - здесь сложность при наивной
линейной организации данных. При использовании деревьев можно, похоже, снизить
до логарифмической, но навскидку описать не могу.
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
