ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Evgenij Masherov                     2:5020/175.2   09 Oct 2002  09:39:59
 To : Alexey Desyatnik
 Subject : Re: Алгоритм
 -------------------------------------------------------------------------------- 
 

 Tue Oct 08 2002 20:26, Alexey Desyatnik wrote to Alexander Pashchenko:
 
  >> Задали тут задачку:
  >> 
  >> Дан массив A[m,n] Известно, что среди его эл-тов
  >> всего 2 равны между собой. Hапечатать их индесксы.
  >> 
  >> Как ее правильно решить.
  >> 
  >> Я так думаю, что надо проходить по матрице и сравнивать текущий элемент с
  >> запомненным, исключая сам запомненный. И если они равны вывести индексы.
  >> Hо вот тут-то я и запутался.
 
  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> имеем в результате _уже_ сложнее полного перебора)
  AD> кроме того, надо учесть и возможности вроде
 
  AD> 1 2  3  4
  AD> 5 6  7  8
  AD> 4 9 10 11
 
  AD> Дальше, думаю, рассматривать не стоит... :)
 
  AD> Сортировка (и тем более хэши) имеют смысл при
  AD> структурах и задачах баз данных, но никак не
  AD> числовых матриц (тем более, как я подозреваю,
  AD> повторный поиск производиться не будет :)
 
 Hу что ж, сравним...
 Прежде всего - зачем обрабатывать каждую строку по отдельности? По условию -
 два одинаковых элемента во всей матрице! При обработке строк по отдельности мы
 скорее всего их пропустим...
 Затем, делаем сортировку всей матрицы
 O(m*n*log(m*n))
 и один проход сравнения
 O(m*n)
 Полагая, что сортировка дает коэффициент сложности по сравнению с лобовой
 реализацией 10 (что ИМХО сильно преувеличение) и принимая размерности матрицы
 1000х1000, получим:
 - лобовая реализация 10^12 операций
 - через сортировку 10*10^6*6=6*10^6 или в примерно 200 000 раз быстрее...
 
 Евгений Машеров АКА СанитарЖеня
 
 --- ifmail v.2.15dev5
  * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
 
 

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

Тема:    Автор:    Дата:    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