Как использование случайности может помочь сделать ваш код быстрее? Лекция Михаила Вялого в Яндексе

[valemak]

Да, есть такое, подбрасывая монетку можно увеличивать эффективность и без того высокоптимизированных алгоритмов.

Классический пример — быстрая сортировка, которую с помощью рандома можно сделать ещё быстрее. Если в подмассивах опорные элементы выбирать не посередине, а в случайном месте, то понятие «вырожденный случай» для quicksort практически теряет смысл…

[chersanya]

Всё-таки случай быстрой сортировки не особо показателен с теоретической точки зрения — без рандома можно сделать quicksort с временем в худшем случае O(n log n). Другое дело, что на практике версия со случайным выбором работает быстрее. Однако, есть ведь алгоритмы, где случайность именно что принципиальна.

[chersanya]

Признаю, забыл про такой факт. Однако, то что я написал в прошлом сообщении верно независимо от этого: я писал, что есть алгоритмы, для которых принципиальна случайность (а также то, что quicksort не является таковым) — а это не отрицает существование детерминированных алгоритмов для той же задачи, которые работают за то же время.

[Salabar]

Всё-равно будет квадрат на массивах типа [a,a,a,a,a,a,a,a,a,a,a,a,a,a...]. Никто не использует ни один алгоритм в чистом виде.

[yeputons]

С чего бы? У нас все элементы равны разделителю и на втором шаге мы радостно запустимся от двух пустых подмассивов. Реализации qsort бывают разные.

[vladob]

[very_light_sarcasm]Еще лет десять и теоретики-алгоритмисты откроют для себя во всей красе теорию вероятностей и математическую статистику. Бог даст, и до баессовских моделей и Gibbs Sampling дойдем.[/very_light_sarcasm]

Я не теоретик, поэтому спрошу здесь — является ли в теории алгоритмов невычислимость (детерминированным образом) достаточным основанием для введения случайности, как последнего средства?

[knagaev]

Посмотрел лекцию с удовольствием.
Понравилась надпись на флипчарте, который стоит рядом с лектором :)
Сразу вспомнилось новость на хабре