Re: Алгоритм

From

Evgenij Masherov (2:5020/175.2)

To

Victor Pogolsha

Date

2002-10-11T09:37:23Z

Area

RU.ALGORITHMS

From: "Evgenij Masherov" <EMasherow@nsi.ru>

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)