Sleep sort

[jayrandom]

И я считаю, что Sleep sort - гениальный алгоритм для сортировки.

Там народ придирается в общем-то к мелочам - "что будет, если я пошлю очень большие числа на сортировку?". Надо просто всё нормализовать в интервал от 0 до 1, это делается за линейное время. Остальная сортировка происходит буквально за секунду.

Самое важное в этом примере - принцип замены измерения пространства измерением времени.
Это прорыв через жестокое O(nlogn), которое так тяготело над компьютерсаенсом.

Comments

[jayrandom.livejournal.com]

В каком месте шучу?

Вообще, конкретная реализация (язык, платформа) - совершенно не важна. Важен принцип взаимопреобразования времени и пространства (памяти), который здесь совершенно шикарно использован.

[livelight]

Вся теория сложности, в рамках которой обычно выводятся оценки вида O(n*log(n)), построена для случая _одного_ вычислителя. Для построения класса алгоритмов NP (известного по NP-полным задачам) вводится специфическое псевдо-распараллеливание с очень ограниченной функциональностью.

В случае, если у нас есть бесконечное количество вычислителей с нулевыми накладными расходами на взаимодействие, вообще всё выглядит по-другому. Например, NP-полная задача взлома хорошего шифра, которая решается путём полного перебора всех возможных ключей (откуда и берётся экспонента по длине ключа) при практически фиксированном времени проверки одного ключа, станет решаться за фиксированное время.

[jayrandom.livejournal.com]

;-)

В реальной жизни у нас не бесконечное количество, а, допустим, m. И важно, как именно для каждого алгоритма это m в формулу впишется.

[livelight]

В реальной жизни у нас не бесконечная память, а, скажем, 4ГБ, позволенные 32-битной архитектурой. А значит, любой массив, какой только может вообразить себе 32-битный компьютер, можно отсортировать за О(1) операций. Это прорыв через жестокое O(nlogn), которое так тяготело над компьютерсаенсом ;)

[jayrandom.livejournal.com]

я оговорился, назвав жизнь реальной :) Имеется в виду та самая мат.модельная реальность, в которой параметр n имеет значение. В ней же, когда обсуждается многопоточность, принято учитывать ограниченное число вычислителей m.