Re: [Q]

From

Sergei Emantayev ()

To

Gimpelson Vadim

Date

2002-09-19T15:23:43Z

Area

RU.ALGORITHMS

From: sergeie@ectel.com (Sergei Emantayev)


"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 операций.
>             Вадим

Суть в том, что мне надо устроить очередь, отсортированную по
некоторому признаку. Сообщения поступают в очередь в _почти_
правильном порядке, так что я не ожидаю много операций поиска. Но все
таки хочется подстраховаться на крайний случай...
Список видится мне наиболее оптимальной структурой, поскольку операции
вставки / удаления с конца - это О(1). А в бинарном дереве - О(log N),
к тому же надо каждый раз балансировать.

Как можно проиндексировать список, чтобы облегчить поиск?

Sergei
--- ifmail v.2.15dev5
 * Origin: http://groups.google.com/ (2:5020/400)