ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Evgenij Masherov                     2:5020/175.2   11 Oct 2002  09:37:23
 To : Victor Pogolsha
 Subject : Re: Алгоритм
 -------------------------------------------------------------------------------- 
 

 Thu Oct 10 2002 11:59, Victor Pogolsha wrote to Egor Alexeev:
 
  
  AD>>> Каждую строку надо просмотреть на наличие двух соседних
  AD>>> элементов (т.е. сложность поднимается _еще_ на m*n,
 
  EA>> И что??? Это же слагаемое. Все равно сложность алгоритма остается
  EA>> O(m*n*log(m*n)), что существенно меньше, чем O((m*n)^2).
 
  VP> Я одного не понимаю... почему лобовая реализация O((m*n)^2)???
  VP> Как я разумею, решение влоб - это последовательное сравнение текущего
  VP> эл-та с _последующими, отбрасывая предыдущие_, а это вовсе не O((m*n)^2).
 
  Я бы рекомендовал ознакомиться со смыслом обозначения О(). 
 Здесь именно O((m*n)^2), поскольку O((m*n)^2)=O((m*n)^2/2)
 
 Евгений Машеров АКА СанитарЖеня
 
 --- ifmail v.2.15dev5
  * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
 
 

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