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