Алгоритм

From

Alexander Chelmodeev (2:5062/17.5)

To

Egor Alexeev

Date

2002-10-10T18:21:43Z

Area

RU.ALGORITHMS

   /Привет Egor!/  
 10 Окт 2002 Чт в 11:51 : Egor Alexeev --> Alexander Chelmodeev:

 EA>>> O(m*n*log(m*n)), что существенно меньше, чем O((m*n)^2).
 AC>>    Я может и ошибаюсь, для 100000 элементов матрицы необходимое
 AC>> количество сравнений равно ~5*10^9, а количество сравнений при
 AC>> использовании QSort посчитать не смог, но в программе больше
 AC>> 1.5*10^6 не получилось. То есть при поиске сортировкой для 100000
 AC>> эл-ов в 3 тыс. раз меньше сравнений. К тому же можно не искать в
 AC>> отсортированном массиве, а внутри цикла сортировки получить
 AC>> требуемое.
 EA> Естественно. Я же именно про это и написал.

   Я только подтвердил цифрами. А вот всё-таки не соображу, как посчитать не
порядок О(), а точно - макс. необходимое кол-во сравнений при сортировке?

... 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: Мышелoвки 'Киш мишь!', пp-вo Узбекиcтaн (2:5062/17.5)