ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alexander Chelmodeev                 2:5062/17.5    10 Oct 2002  19:21:43
 To : Egor Alexeev
 Subject : Алгоритм
 -------------------------------------------------------------------------------- 
 

  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)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Re: Алгоритм   Alexey Desyatnik   08 Oct 2002 20:26:22   Алгоритм   Alexander Pashchenko   09 Oct 2002 00:01:02   Алгоритм   Evgenij Masherov   09 Oct 2002 09:46:57   Re: Алгоритм   Sergey Andrianov   09 Oct 2002 20:27:40   Re: Алгоритм   Andrew Ezhguroff   09 Oct 2002 00:58:14   Re: Алгоритм   Evgenij Masherov   09 Oct 2002 09:39:59   Re: Алгоритм   Alexey Desyatnik   10 Oct 2002 15:12:33   Алгоритм   Egor Alexeev   09 Oct 2002 15:47:10   Алгоритм   Alexander Chelmodeev   09 Oct 2002 23:49:18   Алгоритм   Egor Alexeev   10 Oct 2002 11:51:23   Алгоритм   Alexander Chelmodeev   10 Oct 2002 19:21:43   Алгоритм   Egor Alexeev   13 Oct 2002 12:14:28   Re: Алгоритм   Victor Pogolsha   10 Oct 2002 11:59:56   Алгоритм   Oleg V.Cat   11 Oct 2002 08:26:01   Алгоритм   Egor Alexeev   13 Oct 2002 12:14:32