Sleep sort
И я считаю, что Sleep sort - гениальный алгоритм для сортировки.
Там народ придирается в общем-то к мелочам - "что будет, если я пошлю очень большие числа на сортировку?". Надо просто всё нормализовать в интервал от 0 до 1, это делается за линейное время. Остальная сортировка происходит буквально за секунду.
Самое важное в этом примере - принцип замены измерения пространства измерением времени.
Это прорыв через жестокое O(nlogn), которое так тяготело над компьютерсаенсом.
Там народ придирается в общем-то к мелочам - "что будет, если я пошлю очень большие числа на сортировку?". Надо просто всё нормализовать в интервал от 0 до 1, это делается за линейное время. Остальная сортировка происходит буквально за секунду.
Самое важное в этом примере - принцип замены измерения пространства измерением времени.
Это прорыв через жестокое O(nlogn), которое так тяготело над компьютерсаенсом.