Sleep sort
Oct. 19th, 2011 05:14 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
jayrandomИ я считаю, что Sleep sort - гениальный алгоритм для сортировки.
Там народ придирается в общем-то к мелочам - "что будет, если я пошлю очень большие числа на сортировку?". Надо просто всё нормализовать в интервал от 0 до 1, это делается за линейное время. Остальная сортировка происходит буквально за секунду.
Самое важное в этом примере - принцип замены измерения пространства измерением времени.
Это прорыв через жестокое O(nlogn), которое так тяготело над компьютерсаенсом.
Там народ придирается в общем-то к мелочам - "что будет, если я пошлю очень большие числа на сортировку?". Надо просто всё нормализовать в интервал от 0 до 1, это делается за линейное время. Остальная сортировка происходит буквально за секунду.
Самое важное в этом примере - принцип замены измерения пространства измерением времени.
Это прорыв через жестокое O(nlogn), которое так тяготело над компьютерсаенсом.
no subject
Date: 2011-10-19 09:07 pm (UTC)