Comments 9
Да, есть такое, подбрасывая монетку можно увеличивать эффективность и без того высокоптимизированных алгоритмов.
Классический пример — быстрая сортировка, которую с помощью рандома можно сделать ещё быстрее. Если в подмассивах опорные элементы выбирать не посередине, а в случайном месте, то понятие «вырожденный случай» для quicksort практически теряет смысл…
Классический пример — быстрая сортировка, которую с помощью рандома можно сделать ещё быстрее. Если в подмассивах опорные элементы выбирать не посередине, а в случайном месте, то понятие «вырожденный случай» для quicksort практически теряет смысл…
Всё-таки случай быстрой сортировки не особо показателен с теоретической точки зрения — без рандома можно сделать quicksort с временем в худшем случае O(n log n). Другое дело, что на практике версия со случайным выбором работает быстрее. Однако, есть ведь алгоритмы, где случайность именно что принципиальна.
UFO just landed and posted this here
Признаю, забыл про такой факт. Однако, то что я написал в прошлом сообщении верно независимо от этого: я писал, что есть алгоритмы, для которых принципиальна случайность (а также то, что quicksort не является таковым) — а это не отрицает существование детерминированных алгоритмов для той же задачи, которые работают за то же время.
Всё-равно будет квадрат на массивах типа [a,a,a,a,a,a,a,a,a,a,a,a,a,a...]. Никто не использует ни один алгоритм в чистом виде.
[very_light_sarcasm]Еще лет десять и теоретики-алгоритмисты откроют для себя во всей красе теорию вероятностей и математическую статистику. Бог даст, и до баессовских моделей и Gibbs Sampling дойдем.[/very_light_sarcasm]
Я не теоретик, поэтому спрошу здесь — является ли в теории алгоритмов невычислимость (детерминированным образом) достаточным основанием для введения случайности, как последнего средства?
Я не теоретик, поэтому спрошу здесь — является ли в теории алгоритмов невычислимость (детерминированным образом) достаточным основанием для введения случайности, как последнего средства?
Посмотрел лекцию с удовольствием.
Понравилась надпись на флипчарте, который стоит рядом с лектором :)
Сразу вспомнилось новость на хабре
Понравилась надпись на флипчарте, который стоит рядом с лектором :)
Сразу вспомнилось новость на хабре
Sign up to leave a comment.
Как использование случайности может помочь сделать ваш код быстрее? Лекция Михаила Вялого в Яндексе