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