ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Andrew Ezhguroff                     2:5020/400     11 Oct 2002  02:48:33
 To : Victor Pogolsha
 Subject : Re: Алгоритм
 -------------------------------------------------------------------------------- 
 

 Привет! "Victor Pogolsha" <Victor.Pogolsha@p12.f57.n5003.z2.fidonet.org>
 сообщил(а):
 
  VP> Я одного не понимаю... почему лобовая реализация O((m*n)^2)???
  VP> Как я разумею, решение влоб - это последовательное сравнение текущего
  VP> эл-та с _последующими, отбрасывая предыдущие_, а это вовсе не
  VP> O((m*n)^2).
 
 Hемного арифметики... Hа первом проходе понадобится 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. Hо
 (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)
 
 

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