ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Ilya Teterin                         2:5020/400     08 Apr 2003  18:31:31
 To : Val Krigan
 Subject : Re: Сортировка
 -------------------------------------------------------------------------------- 
 

 Tue Apr 08 2003 18:15, Val Krigan wrote to Ilya Teterin:
 
  VK> Да, выигрыш _только_ если алфавит меньше исходного массива, или алфавит
  VK> извесен заранее. Иначе быстрее quicksort вроде ничего быть не может
 
 Может-может.
 
  >> В моем же алгоритме сложность O(n) достигается, если hash_func построена с
  >> учетом заранее известного распределения входных данных, что имхо гораздо
  >> более  реальная ситуация.
 
  VK> Хмм... а это не ты случайно написал?
 
 Да я вроде...
 
  VK> for(i=0;i<nodes.size();i++){
  VK> sort_node(nodes[i]);
 
 При hash_space=n и удачном выборе hash_func длина nodes[i] будет равна 1 для
 любого i, соотв., sort_node(nodes[i]) будет иметь сложность O(1), и наконец
 весь кусок кода будет иметь сложность O(n). Ы?
 
 --- ifmail v.2.15dev4
  * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)
 
 

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