ru.algorithms

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

 "Ilya Teterin" wrote
 
 >  VK> Это зашифрованный "log", опечатался, пардон :)
 >
 > Я в первый раз так и подумал, но когда увидел этого лоха второй раз, начал
 > сомневаться :)
 
 Второй раз была цитата, я не стал править.
 > Hу так к чему мы пришли... У твоего алгоритма сложность O(n+m*log(m)).
 > Получается, что выигрыш по сравнению с quicksort'ом будет только при каких-то
 > сильно специфических входных данных, у которых m<<n, или же у совсем
 > специфических, когда алфавит "заранее известен". Ы?
 
 Да, выигрыш _только_ если алфавит меньше исходного массива, или алфавит извесен
 заранее. Иначе быстрее quicksort вроде ничего быть не может
 
 > В моем же алгоритме сложность O(n) достигается, если hash_func построена с
 > учетом заранее известного распределения входных данных, что имхо гораздо более
 > реальная ситуация.
 
 Хмм... а это не ты случайно написал?
 
 for(i=0;i<nodes.size();i++){
 sort_node(nodes[i]);
 --- ifmail v.2.15dev4
  * Origin: Demos online service (2:5020/400)
 
 

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