ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Andrew Ezhguroff                     2:5020/400     09 Oct 2002  00:58:14
 To : Alexey Desyatnik
 Subject : Re: Алгоритм
 -------------------------------------------------------------------------------- 
 

 Привет! "Alexey Desyatnik" <desyatnik@dax.ru>  сообщил(а):
 
  AD> Вопреки предлагаемому массив сортировать HЕ надо.
 
 Ошибаешься.
 
  AD> Почему? При неотсортированном массиве алгоритм очевиден -
  AD> перебор с ограничением (в худшем случае будем сравнивать
  AD> каждый элемент с каждым). Сложность алгоритма О((m*n)^2).
 
 Ага.
 
  AD> Теперь рассмотрим сортировку - неважно какой алгоритм.
  AD> Линейного-то все равно не существует, в лучшем случае
  AD> O(n*log(n)). Сортировать придется каждую строку (или
  AD> столбец), т.е. для всей матрицы поимеем сложность уже
  AD> O(m*n*log(n)) (или, соотв., O(n*m*log(m))). Далее,
  AD> рассмотрим худший случай, например (после сортировки):
  AD> 1  2  3  4
  AD> 5  6  7  8
  AD> 9 10 11 11
  AD> Каждую строку надо просмотреть на наличие двух соседних
  AD> элементов (т.е. сложность поднимается _еще_ на m*n,
  AD> имеем в результате _уже_ сложнее полного перебора)
 
 А вот здесь уже ошибаешься: O(m*n*ln(n))+O(m*n) равно O(m*n*ln(n)), что
 много меньше, чем O(m*n*m*n) полного перебора.
 
  AD> кроме того, надо учесть и возможности вроде
  AD> 1 2  3  4
  AD> 5 6  7  8
  AD> 4 9 10 11
  AD> Дальше, думаю, рассматривать не стоит... :)
 
 Стоит. Сортировать надо не матрицу A[m, n], а ВЕКТОР A[m*n]. В этом случае
 сортировка займет O(m*n*ln(m*n)), а поиск - O(m*n). Что в сумме дает
 O(m*n*ln(m*n)) - опять много меньше, чем O(m*n*m*n).
 
 С уважением, Андрей.
 -- 
 Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
 --- ifmail v.2.15dev5
  * Origin: Talk.Mail.Ru (2:5020/400)
 
 

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

Тема:    Автор:    Дата:    Re: Алгоритм   Alexey Desyatnik   08 Oct 2002 20:26:22   Алгоритм   Alexander Pashchenko   09 Oct 2002 00:01:02   Алгоритм   Evgenij Masherov   09 Oct 2002 09:46:57   Re: Алгоритм   Sergey Andrianov   09 Oct 2002 20:27:40   Re: Алгоритм   Andrew Ezhguroff   09 Oct 2002 00:58:14   Re: Алгоритм   Evgenij Masherov   09 Oct 2002 09:39:59   Re: Алгоритм   Alexey Desyatnik   10 Oct 2002 15:12:33   Алгоритм   Egor Alexeev   09 Oct 2002 15:47:10   Алгоритм   Alexander Chelmodeev   09 Oct 2002 23:49:18   Алгоритм   Egor Alexeev   10 Oct 2002 11:51:23   Алгоритм   Alexander Chelmodeev   10 Oct 2002 19:21:43   Алгоритм   Egor Alexeev   13 Oct 2002 12:14:28   Re: Алгоритм   Victor Pogolsha   10 Oct 2002 11:59:56   Алгоритм   Oleg V.Cat   11 Oct 2002 08:26:01   Алгоритм   Egor Alexeev   13 Oct 2002 12:14:32