ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Val Krigan                           2:5020/400     09 Apr 2003  01:28:35
 To : Dmitriy Goldobin
 Subject : Re: Сортировка
 -------------------------------------------------------------------------------- 
 

 "Dmitriy Goldobin" wrote
 
 > > hash<float,intZ>    cont;
 > >
 > > // заносим, сложность O(N)
 > > for(i=0; i<N; i++)
 > >     cont[p[i]].second++;
 >
 > А почему тун O(N)? Что это за алгоритм, позволяющий получить хоть и не
 > сортированный, но однозначный маппинг со сложностью O(N)?
 
 Это так называемый "хеш". Поиск соответствия занимает константное время,
 независимо от  размеров массива. Мы делаем это N раз. Отсюда и O(N).
 --- ifmail v.2.15dev4
  * Origin: Demos online service (2:5020/400)
 
 

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