ru.perl

 
 - RU.PERL ----------------------------------------------------------------------
 From : Andrey Sapozhnikov                   2:5020/400     11 Nov 2002  19:22:57
 To : Eugene Grosbein
 Subject : Re: двоичный поиск
 -------------------------------------------------------------------------------- 
 

 Eugene Grosbein wrote:
 
 >  ISC> Может лучше в hash их затолкать - тогда, наверное, и алгоритьм проще
 >  ISC> будет и
 >  ISC> бестрее искаться ...
 > hash хуже бинарного поиска.
 
 Это неправда. Binary search (или он же поиск в упорядоченном
 линейном массиве методом половинного деления) имеет скорость
 O(log n), что конечно лучше Linear search (он же поиск перебором)
 с его O(n), но hash search имеет скорость O(1) (для perfect hashes,
 для perl hashes более точно - O(1 + a) где a - load factor равный n/m,
 и соответственно m - число слотов. Однако perl поддерживает число слотов
 
  >= n динамически и функция близка к O(1 + 1) что есть тоже самое, что
 
 и O(1)). Разумеется, можно исскуственно подобрать вырожденые значения
 ключей для которых hash-функция даст одинаковый результат, однако
 без специального подбора вероятность попадания большого множества
 ключей в один слот исчезающе мала.
 
 Андрей
 
 --- ifmail v.2.15dev5
  * Origin: Demos online service (2:5020/400)
 
 

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