Если вы программист, то вы определенно пытались решить одну или несколько задач на таких сайтах, как Leetcode или Codeforces.
Как вы знаете, большинство из этих задач требуют точного ответа в каждом тестовом примере, но представляли ли вы, что некоторые из этих проблем могут быть решены с помощью решений, которые используют случайную функцию для получения точных результатов?
И верите вы или нет, вам может очень не повезти и вы получите неправильный ответ в конце, даже если ваше решение верное
В мире алгоритмов есть некоторые из них, которые используют своего рода случайность при выборе подходящего решения. Эти алгоритмы называются рандомизированными алгоритмами.
Эти алгоритмы обычно используются разработчиками, и сегодня мы рассмотрим, как они могут использовать при решении задач.
Удивительно то, что эти алгоритмы можно использовать в очень строгой области, такой как решение проблем, области, которая может определить ваш код как неправильный, если вы прошли 99% тестовых случаев, а не все из них. Честно говоря, их не так часто используют для решения проблем, но все же есть много проблем, для решения которых нужна эта случайность.
Мне всегда нравится брать эту проблему в качестве примера:
допустим, у нас есть количество точек, все они представлены как (x, y), и вам нужно найти максимальное количество точек, которые могут лежать на одной линии.
Важное примечание: несомненно, что не менее четверти точек лежат на одной линии
поэтому ответ будет не менее 1/4 от количества точек
До примечания это было похоже на обычную задачу по геометрии, но в примечании она отличалась от любой другой задачи, с которой вы могли сталкиваться раньше.
Регулярное решение (грубая сила):
Базовое правило геометрии состоит в том, что для построения линии нужно как минимум две точки. указать и перебрать все оставшиеся точки и попытаться найти максимальное количество точек на одной линии
В чем проблема?
Этот подход займет много времени, потому что сложность выбора двух точек является факториальной, отличной от сложности цикла по оставшимся точкам
Сложность времени O(!n*n)
Лучшее решение (с использованием случайных точек)
Ключом к этой проблеме являются вероятности. Мы ищем идеальную линию (на которой есть максимальное количество точек)
предположим, что мы выбираем случайную точку A , с помощью простой математики и вероятностей мы можем видеть, что вероятность того, что эта точка находится на идеальной линии, составляет 1/4 .
К сожалению, одной точки недостаточно для описания линии, которая нам нужна в минимум две точки
Итак, давайте случайным образом выберем пару точек и предположим, что эта пара лежит на идиальной линии, вероятность этого равна 1/16
Математически, это означает если мы выбрали 16 случайных пар, у нас будет по крайней мере одна из пар, лежащих на идиальной линии, что приведет нас к нахождению самой линии.
Как мы решили проблему сложности?:
После выбора определенного количества попыток для пары точек мы избавились от факторной сложности, и теперь у нас есть постоянное число. Таким образом, окончательная сложность решения этой проблемы составляет O (n)
Достаточно ли этого?
Математически достаточно
Выбрав пару точек 16 раз, я буду уверен, что проблема будет решена
но может быть шанс иметь худшую удачу когда-либо, и я знаю, что не принято говорить об удаче в решении проблем, но, как я уже сказал, это не обычная тема
Хотя решение зависит от случайности и удачи (если правильно сказать, удачи), вы можете попытаться увеличить вероятность нахождения правильной пары, сделав что-то вроде предотвращения повторения пар, поскольку вам не нужно проверять одно и то же. пара дважды, а затем снова перебрать все точки
Вы также можете использовать что-то вроде timer , поэтому, если время решения проблемы составляет, например, 4 секунды, вы можете попробовать любое количество пар, пока время прогона не будет почти 4 секунды, после чего вы можете прекратить попытки и распечатать результат
Теперь, если вы хотите реализовать решение проблемы, я создал его на hackerrank с несколькими тестовыми примерами для проверки вашего кода, вы можете попробовать его здесь https://www.hackerrank.com/contests/contest44-1/challenges.
