ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alexey Desyatnik                     2:5020/400     08 Oct 2002  20:26:22
 To : Alexander Pashchenko
 Subject : Re: Алгоритм
 -------------------------------------------------------------------------------- 
 

 Alexander Pashchenko пишет:
 
 > Задали тут задачку:
 > 
 > Дан массив A[m,n] Известно, что среди его эл-тов
 > всего 2 равны между собой. Hапечатать их индесксы.
 > 
 > Как ее правильно решить.
 > 
 > Я так думаю, что надо проходить по матрице и сравнивать текущий элемент с
 > запомненным, исключая сам запомненный. И если они равны вывести индексы.
 > Hо вот тут-то я и запутался.
 
 Вопреки предлагаемому массив сортировать HЕ надо.
 Почему? При неотсортированном массиве алгоритм очевиден -
 перебор с ограничением (в худшем случае будем сравнивать
 каждый элемент с каждым). Сложность алгоритма О((m*n)^2).
 
 Теперь рассмотрим сортировку - неважно какой алгоритм.
 Линейного-то все равно не существует, в лучшем случае
 O(n*log(n)). Сортировать придется каждую строку (или
 столбец), т.е. для всей матрицы поимеем сложность уже
 O(m*n*log(n)) (или, соотв., O(n*m*log(m))). Далее,
 рассмотрим худший случай, например (после сортировки):
 
 1  2  3  4
 5  6  7  8
 9 10 11 11
 
 Каждую строку надо просмотреть на наличие двух соседних
 элементов (т.е. сложность поднимается _еще_ на m*n,
 имеем в результате _уже_ сложнее полного перебора)
 кроме того, надо учесть и возможности вроде
 
 1 2  3  4
 5 6  7  8
 4 9 10 11
 
 Дальше, думаю, рассматривать не стоит... :)
 
 Сортировка (и тем более хэши) имеют смысл при
 структурах и задачах баз данных, но никак не
 числовых матриц (тем более, как я подозреваю,
 повторный поиск производиться не будет :)
 
 WBR, AD (desyatnik@dax.ru)
 -- 
 Отправлено через сервер Форумы@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