|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrew Ezhguroff 2:5020/400 27 Sep 2002 21:38:37
To : Sergei Emantayev
Subject : Re: [Q]
--------------------------------------------------------------------------------
Привет! "Sergei Emantayev" <sergeie@ectel.com> сообщил(а):
SE> Суть в том, что мне надо устроить очередь, отсортированную по
SE> некоторому признаку. Сообщения поступают в очередь в _почти_
SE> правильном порядке, так что я не ожидаю много операций поиска. Hо все
SE> таки хочется подстраховаться на крайний случай...
Если данные не отсортированы ("почти отсортировано" здесь не проходит), то и
массиве поиск займет O(N).
SE> Список видится мне наиболее оптимальной структурой, поскольку операции
SE> вставки / удаления с конца - это О(1).
И время поиска O(N).
SE> А в бинарном дереве - О(log N)
Hо и поиск - O(log(N))
SE> , к тому же надо каждый раз балансировать.
Балансировать надо бинарные деревья. B-tree в балансировке не нуждаются.
С уважением, Андрей.
--
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
* Origin: Talk.Mail.Ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
