ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Sergey Andrianov                     2:5020/1507.400 09 Oct 2002  20:27:40
 To : Alexander Pashchenko
 Subject : Re: Алгоритм
 -------------------------------------------------------------------------------- 
 

 
 Однажды 09-Oct-02  в 00:01   Alexander Pashchenko (2:5062/17.212)
 написал       desyatnik@dax.ru    по поводу
 -=-   Алгоритм  -=-
 
 AD>> Вопреки предлагаемому массив сортировать HЕ надо.
 AD>> Почему? При неотсортированном массиве алгоритм очевиден -
 AD>> перебор с ограничением (в худшем случае будем сравнивать
 AD>> каждый элемент с каждым). Сложность алгоритма О((m*n)^2).
 AP> Kстати, я так и не разобрался, что сие  ^^^^^^^^^^^^^^^^^^^^ значит. Может 
 AP> кто-нить объяснить доступными для понимания (10-11 класс) словами.
 
   Если количество операций или время (что то же самое) при выполнении алгоритма 
 при больших n ведет себя как C*F(n), где С - константа , то говорят, что
 сложность алгоритма O(F(n)). При этом принято, что F(n) не должна содержать
 слагаемых. Hапример A*x^2 + B*x + C имеет сложность O(x^2), т.к. при больших n
 линейный член и константа становятся исчезающе малы по сравнению с квадратичным 
 членом.
 
 AD>> Теперь рассмотрим сортировку - неважно какой алгоритм.
 AP> [skip]
 AD>> 4 9 10 11
 AP> Скорость абсолютно не важна. Главное, чтобы было понятно и изящно.
 
   Обыно считается, что "изящно" должно включать в себя "быстро".
  
 AP> В голову лезут только вложенные циклы с исключением пройденных элементов, 
 AP> но что-то мне подсказывает, что там бага, к тому же это далеко не изящно.
 AD>> Дальше, думаю, рассматривать не стоит... :)
 AP> Да и вопрос-то был теоритический.
 AD>> Сортировка (и тем более хэши) имеют смысл при
 AD>> структурах и задачах баз данных, но никак не
 AD>> числовых матриц (тем более, как я подозреваю,
 AD>> повторный поиск производиться не будет :)
 AP> ЗЫ а вдобавок доступно объяснить, что такое хэш?
 
   Один из способов увеличить скорость за счет расхода дополнительной памяти. 
   Hу, тебе это не интересно... :)
                   До свидания,  в  20:20 MSK
                                  Sergey
 
 ---
  * Origin: Sergiev Posad (2:5020/1507.400)
 
 

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

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