ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Nick Kovaliov                        2:5020/400     17 Feb 2003  09:57:35
 To : Aleksey Vaneev
 Subject : Re: Максимум в "бегущем окне"
 -------------------------------------------------------------------------------- 
 

     AV> Задачка такая вылезла. Имеется поток цифр.
     AV> В каждый момент времени пополняется одним элементом.
     AV> Также в каждый момент времени рассматривается
     AV> окно, "накрывающее" N прошедших элементов.
     AV> Дана задача определить в каждый момент времени
     AV> максимальную цифру в окне, а также ее индекс.
     AV> Каким быстрым способом можно решить эту задачу?
     AV> Отсортированный динамически изменяющийся
     AV> двусвязный список, а также "поголовная"
     AV> проверка элементов - самые медленные решения.
 
 Организуй данные в виде кучи (heap),
 в худшем случае время работы log(N).
 Или сделай, как советует Евгений Машеров,
 В среднем должно быть быстрее
 (за счёт более быстрой вставки).
 
 До встречи, всего наилучшего !
 --- ifmail v.2.15dev5
  * Origin: Demos online service (2:5020/400)
 
 

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

Тема:    Автор:    Дата:    Максимум в "бегущем окне"   Aleksey Vaneev   13 Feb 2003 23:54:05   Re: Максимум в " бегущем окне"   Oleg I. Khovayko   14 Feb 2003 19:00:09   Максимум в "бегущем окне"   Evgenij Masherov   14 Feb 2003 21:14:42   Re: Максимум в "бегущем окне"   Oleg Schmidt   15 Feb 2003 00:45:33   Re: Максимум в "бегущем окне"   Nick Kovaliov   17 Feb 2003 09:57:35