Re: Алгоритм

From

Andrew Ezhguroff ()

To

Alexey Desyatnik

Date

2002-10-09T00:58:14Z

Area

RU.ALGORITHMS

From: "Andrew Ezhguroff" <eandr@com2com.ru>

Привет! "Alexey Desyatnik" <desyatnik@dax.ru>  сообщил(а):

 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> имеем в результате _уже_ сложнее полного перебора)

А вот здесь уже ошибаешься: 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)