ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Boris Sivko                          2:452/26.14    01 Feb 2002  19:06:05
 To : Sergey Politov
 Subject : муха
 -------------------------------------------------------------------------------- 
 

 
     Дело "Re: муха" было в Пятница Февраль 01 2002 06:17 и заведено оно от
 Sergey Politov к Boris Sivko, но мне кажется, что в нём не хватало нескольких
 строк:
 
  SP> [...]
  BS>>   То же самый алгоритм, только дискретность вытекает по положению
  BS>> мух,
  SP> [...]
  BS>> O(m*n)+O(n*log n) -> O(m*n).
  SP> Да и размер мухобойки динамически изменяется?
 
   Откуда такие выводы? ??
   У нас имеется сетка, образованная положениями мух. Если идём слева направо, то
 сначала отбрасываем мух, касающихся левой стороны и двигаем мухобойку на вправо 
 на одну позицию сетки. Смотрим, сколько мух добавилось в результате
 передвижения.
 
  SP> С вещественными тут не проходит ибо при перемещении к следующему
  SP> столбцу мы можем открыть сразу несколько. Hо самое интересное
  SP> начинается когда никакие две мухи не находятся на одной горизонтали и
  SP> вертикали. Там может и памяти начать не хватать. Ее там O(n^2) надо.
 
   Почему O(n^2) ??
   Hам всего лишь нужно знать значения сетки по координатам : (m+n).
 
   Решение как у Максима получается, но откуда он взял O(n^3)? Вроде как перебор 
 O(n^2) даёт.
 
      Счастливо, Sergey. Вспоминай обо мне...
 ... I'll be back...
  * Origin: у страна! у народ! (2:452/26.14)
 
 

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

Тема:    Автор:    Дата:    муха   Anton Svatkov   29 Jan 2002 13:22:30   муха   Max Alekseyev   29 Jan 2002 18:23:10   Re: муха   Sergey Politov   30 Jan 2002 07:17:38   муха   Anton Svatkov   31 Jan 2002 18:57:59   муха   Boris Sivko   01 Feb 2002 00:55:55   Re: муха   Sergey Politov   01 Feb 2002 07:17:13   муха   Boris Sivko   01 Feb 2002 19:06:05   Re: муха   Sergey Politov   02 Feb 2002 07:25:24   муха   vitalie vrabie   23 Feb 2002 03:00:20   Re: муха   Sergey Politov   01 Feb 2002 07:17:49