ru.algorithms

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

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

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