Re: Алгоритм

From

Evgenij Masherov (2:5020/175.2)

To

Alexey Desyatnik

Date

2002-10-09T09:39:59Z

Area

RU.ALGORITHMS

From: "Evgenij Masherov" <EMasherow@nsi.ru>

Tue Oct 08 2002 20:26, Alexey Desyatnik wrote to Alexander Pashchenko:

 >> Задали тут задачку:
 >> 
 >> Дан массив A[m,n] Известно, что среди его эл-тов
 >> всего 2 равны между собой. Напечатать их индесксы.
 >> 
 >> Как ее правильно решить.
 >> 
 >> Я так думаю, что надо проходить по матрице и сравнивать текущий элемент с
 >> запомненным, исключая сам запомненный. И если они равны вывести индексы.
 >> Но вот тут-то я и запутался.

 AD> Вопреки предлагаемому массив сортировать НЕ надо.
 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> повторный поиск производиться не будет :)

Ну что ж, сравним...
Прежде всего - зачем обрабатывать каждую строку по отдельности? По условию -
два одинаковых элемента во всей матрице! При обработке строк по отдельности мы
скорее всего их пропустим...
Затем, делаем сортировку всей матрицы
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)