ru.algorithms

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

 Hi!
 
 > > Хэш не дает однозначного соответствия на произвольном наборе данных. То
 > есть
 > > если это хэш в традиционном понимании, то нескольким разным float
 > > соответствует один intZ, если же это просто хешированный набор, то у
 
 него
 
 > > сложность отнюдь не O(N).
 >
 > В плохом случае не дает. HО при использовании хорошего генератора
 
 случайных
 
 > чисел на подавляющем большинстве данных результат будет именно O(N).
 
 Потому,
 
 > что нескольким float соответствует один intZ, просто число таких float
 > приходящихся на один intZ невелико и не зависит от размеров массива.
 
 Размер
 
 > хеш-таблицы зависит.
 
 Дак и у Тетерина абсолютно то же самое, если с хэш-функцией "повезет" на
 данном наборе, то будет O(N), а если не повезет и для всего набора
 хэш-функция выдаст одно и то же значение, то будет от O(N*logN) до O(N*N/2).
 Ведь твой cont[p[i]] на практике что означает?
 
 somelist = hashTable[hashFunc(p[i])];
 if( !search( somelist, p[i] ) ) insert( somelist, p[i] );
 
 то есть выборка по хэшу O(N), но search/insert уже зависит от распределения
 данных в хэшe и не может быть O(1) независимо от того, что ты используешь в
 качестве somelist. В общем случае search/insert будет медленнее чем
 push_back с последующим qsort у Тетерина. А по сути это один и тот же
 алгоритм, за исключением того, что он еще и hashFunc предлагает выбрать
 упорядоченную, чтобы избежать последующей сортировки.
 
 Hасчет генератора случайных чисел применительно к хэшу я что-то не уловил.
 
 Bye.
 --- ifmail v.2.15dev4
  * Origin: Demos online service (2:5020/400)
 
 

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