Просмотр исходного текста страницы Временная и пространственная сложность алгоритмов/Задачи/замки и ключи

<latex>
Дано n ключей и n замков. Все ключи и все замки различны между собой, а каждый ключ подходит к единственному замку. Ключи (и замочные скважины) упорядочены по величине, но визуально отличия неразличимы. На каждом шаге можно попытаться вставить конкретный ключ в конкретный замок и заключить, что он подходит или больше, или меньше искомого. Постройте вероятностный алгоритм подбора ключей, требующий в среднем o( $n^2$ ) шагов


Комментарий. Очевидно, что прямой перебор подходящих пар ключей и замков требует квадратичного числа шагов. Удивительным кажется то, что для этой задачи построен
детерминированный o( $n^2$ )-алгоритм. Он очень хитрый.
</latex>

[[Категория:Решенные задачи]]