Re: Алгоритм

From

Andrew Ezhguroff ()

To

Victor Pogolsha

Date

2002-10-11T02:48:33Z

Area

RU.ALGORITHMS

From: "Andrew Ezhguroff" <eandr@com2com.ru>

Привет! "Victor Pogolsha" <Victor.Pogolsha@p12.f57.n5003.z2.fidonet.org>
сообщил(а):

 VP> Я одного не понимаю... почему лобовая реализация O((m*n)^2)???
 VP> Как я разумею, решение влоб - это последовательное сравнение текущего
 VP> эл-та с _последующими, отбрасывая предыдущие_, а это вовсе не
 VP> O((m*n)^2).

Немного арифметики... На первом проходе понадобится m*n-1 сравнений, на
втором m*n-2, на m*n-2 проходе - 2 сравнения, на m*n-1 проходе - 1 одно
сравнение. Имеем арифметическую прогрессию от 1 до m*n-1 с шагом 1. Ее сумма
равна (m*n)*(m*n-1)/2 - это кол-во сравнений в худшем случае. В среднем
кол-во сравнений будет вдвое меньше - (m*n)*(m*n-1)/4. Но
(m*n)*(m*n-1)/4=((m*n)^2)/4-m*n/4 - это и есть O((m*n)^2).

С уважением, Андрей.



-- 
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
 * Origin: Talk.Mail.Ru (2:5020/400)