Re: Алгоритм

From

Alexey Desyatnik ()

To

Alexander Pashchenko

Date

2002-10-08T20:26:22Z

Area

RU.ALGORITHMS

From: Alexey Desyatnik <desyatnik@dax.ru>

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

Вопреки предлагаемому массив сортировать НЕ надо.
Почему? При неотсортированном массиве алгоритм очевиден -
перебор с ограничением (в худшем случае будем сравнивать
каждый элемент с каждым). Сложность алгоритма О((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)