|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergei Emantayev 2:5020/400 19 Sep 2002 15:23:43
To : Gimpelson Vadim
Subject : Re: [Q]
--------------------------------------------------------------------------------
"Gimpelson Vadim" <zca187@sectorb.msk.ru> wrote in message
news:<amaqc8$1jlj$1@ddt.demos.su>...
> "Sergei Emantayev" <sergeie@ectel.com> wrote in message
> news:86bab0ea.0209180228.73d8d134@posting.google.com...
> >
> > Вот есть у меня отсортированный список. Пускай даже двух-связный.
> > Существуют ли алгоритмы быстрого поиска (> O(n)) для списка?
> >
> > Sergei.
> А проиндексировать список никак нельзя? Иначе нельзя так как чтобы добраться
> до последнего елемента надо n операций.
> Вадим
Суть в том, что мне надо устроить очередь, отсортированную по
некоторому признаку. Сообщения поступают в очередь в _почти_
правильном порядке, так что я не ожидаю много операций поиска. Hо все
таки хочется подстраховаться на крайний случай...
Список видится мне наиболее оптимальной структурой, поскольку операции
вставки / удаления с конца - это О(1). А в бинарном дереве - О(log N),
к тому же надо каждый раз балансировать.
Как можно проиндексировать список, чтобы облегчить поиск?
Sergei
--- ifmail v.2.15dev5
* Origin: http://groups.google.com/ (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
