|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Ilya Teterin 2:5020/400 08 Apr 2003 10:41:01
To : Val Krigan
Subject : Re: Сортировка
--------------------------------------------------------------------------------
Tue Apr 08 2003 09:45, Val Krigan wrote to Ilya Teterin:
>> Я тут знакомых поспрашивал, никто не знает функцию loh :( Это что? И,
VK> Это зашифрованный "log", опечатался, пардон :)
Я в первый раз так и подумал, но когда увидел этого лоха второй раз, начал
сомневаться :)
Hу так к чему мы пришли... У твоего алгоритма сложность O(n+m*log(m)).
Получается, что выигрыш по сравнению с quicksort'ом будет только при каких-то
сильно специфических входных данных, у которых m<<n, или же у совсем
специфических, когда алфавит "заранее известен". Ы?
В моем же алгоритме сложность O(n) достигается, если hash_func построена с
учетом заранее известного распределения входных данных, что имхо гораздо более
реальная ситуация.
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
