Алгоритм

From

Alexander Chelmodeev (2:5062/17.5)

To

Egor Alexeev

Date

2002-10-09T22:49:18Z

Area

RU.ALGORITHMS

   /Привет Egor!/  
 09 Окт 2002 Сp в 15:47 : Egor Alexeev --> Alexey Desyatnik:

 AD>> Каждую строку надо просмотреть на наличие двух соседних
 AD>> элементов (т.е. сложность поднимается _еще_ на m*n,
 EA> И что??? Это же слагаемое. Все равно сложность алгоритма остается
 EA> O(m*n*log(m*n)), что существенно меньше, чем O((m*n)^2).

   Я может и ошибаюсь, для 100000 элементов матрицы необходимое количество
сравнений равно ~5*10^9, а количество сравнений при использовании QSort
посчитать не смог, но в программе больше 1.5*10^6 не получилось. То есть при
поиске сортировкой для 100000 эл-ов в 3 тыс. раз меньше сравнений. К тому же
можно не искать в отсортированном массиве, а внутри цикла сортировки получить
требуемое.

... http://ichip.rbcmail.ru  ... mailto: ichip(a)rbcmail.ru
--- GoldED+/386 1.1.5-20010807 rev.0813 (MS-DOS 7.10 pc) * Chip&Deal *
 * Origin: В cепapaтнoм дoгoвopе не ищи cпacения. (2:5062/17.5)