ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alexander Chelmodeev                 2:5062/17.5    09 Oct 2002  23:49:18
 To : Egor Alexeev
 Subject : Алгоритм
 -------------------------------------------------------------------------------- 
 

  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)
 
 

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

Тема:    Автор:    Дата:    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