Ответом ко вчерашней загадке был вероятностный алгоритм – и уж извините за то, что не втиснул в условие, что решение должно быть почти достоверным. 💁♂️
Почти достоверность позволяет нам ценой редких ошибок на порядки снижать сложность разных алгоритмов. Собственно, из подобных алгоритмов и пошло название канала epsilon correct, хотя правильнее, конечно, было бы назваться 1-ε correct. Но как мы можем из "хоть сколько-нибудь" достоверного алгоритма сделать почти достоверный?👀
Допустим, нам дан алгоритм
В случае бинарных исходов, для конкретных значений вероятности δ и ошибки ε результат медианного алгоритма следует биномиальному распределению, так что можно посчитать количество требуемых попыток точно.👌
Почти достоверность позволяет нам ценой редких ошибок на порядки снижать сложность разных алгоритмов. Собственно, из подобных алгоритмов и пошло название канала epsilon correct, хотя правильнее, конечно, было бы назваться 1-ε correct. Но как мы можем из "хоть сколько-нибудь" достоверного алгоритма сделать почти достоверный?
Допустим, нам дан алгоритм
A с выходами A(x)∊R. Например, A(x)∊{0,1} – x сортированный или нет. И если A выдаёт правильный ответ с вероятностью δ=51%, мы хотим эту веростность довести до (1-ε). Оказывается, этого можно достичь, если мы (независимо) выполним наш алгоритм O(log(1/ε)) раз и возьмём медианный результат. Доказательство можно посмотреть вот тут.В случае бинарных исходов, для конкретных значений вероятности δ и ошибки ε результат медианного алгоритма следует биномиальному распределению, так что можно посчитать количество требуемых попыток точно.