ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Sergiy Kanilo                        2:5020/400     09 Apr 2002  20:38:43
 To : Oleg I. Khovayko
 Subject : Re: Поиск
 -------------------------------------------------------------------------------- 
 

 "Oleg I. Khovayko" <olegh@ncbi.nlm.nih.gov> wrote in message
 news:3CB304D2.174DF45B@ncbi.nlm.nih.gov...
 
 > Alexey Zhivotov wrote:
 > >  имеем двунаправленный список с 10000 строк отсортированных по алфавиту.
 > > Инересует пример не очень сложного в реализации, но более быстрого, чем
 
 тупое
 
 > > сравнение каждый-скаждым,  алгоритма по нахождению в этом списке всех
 > > одинаковых строк.
 >
 > А зачем же сравнивать "каждый-с-каждым"? Если список отсортирован, то
 
 каждый
 
 > элемент надо сравнить только с предыдущим (ну или последующим). И все!
 > То есть { число сравнений = N - 1 }, где N - число элементов в твоем
 
 списке.
 
 > И это оптимальное решение...
 
 Если в последовательности встречаются большие группы одинаковых
 элементов, то после нахождения пары одинаковых элементов можно
 начинать прыгать через элементы с увеличивающимся шагом 2,4,8, и т.д,
 и если повторяющихся элементов много - то этим можно выиграть
 несколько сравнений.
 Так напимер, в коайнем случае, если все элементы одинаковы, число
 сравнений пропорционально lnN.
 
 Cheers,
 Serge
 --- ifmail v.2.15dev5
  * Origin: Sent via Graf's Inn at news://news.relhum.org (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Re: Поиск   Oleg I. Khovayko   09 Apr 2002 19:13:51   Re: Поиск   Sergiy Kanilo   09 Apr 2002 20:38:43   Re: Поиск   Sergey Andrianov   11 Apr 2002 21:40:02   Re: Поиск   Sergiy Kanilo   14 Apr 2002 22:00:34   Re^2: Поиск   Alexey Zhivotov   10 Apr 2002 11:04:38