|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Ilia Kantor 2:5020/175.2 19 Feb 2003 01:18:47
To : Stanislav Shwartsman
Subject : Quick Sort
--------------------------------------------------------------------------------
Mon Feb 17 2003 08:12, Stanislav Shwartsman wrote to Ilia Kantor:
SS>>>> Доказательство говорит, что быстрее, чем O(NlogN) не бывает. А
SS>>>> константу сделать получше, чем в Quick Sort IMHO очень даже возможно
SS>>>> ...
SMP>>> А какая она там, кстати? Лень в Кнута лезть.
IK>> А она от компутера зависит и от компилера просто немеряно.
IK>> Квиксорт это клева ваще.
SS> Тот QuickSort, который я помню, вообще был рандомный и давал свои
SS> O(NlogN)
SS> только в среднем случае, а в худшем и все О(N^2).
SS> Правда вроде есть и детерминистическая реализация ...
Hе слышал о такой. С рандомизированными алгоритмами прикол в том, что
вероятность работы квиксорта за ~O(N^2) при, скажем, N>10000 гораздо меньше,
чем вероятность того, что в момент вычисления компьютер банально перегорит.
Или операционная система сглючит.. Или еще что.. Поэтому в расчет такое
попросту не принимают и прально делают.
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
