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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: «Category:Предложенные студентами задачи <latex> Дано n ключей и n замков. Все ключи и все замки…»)
 
Строка 1: Строка 1:
[[Category:Предложенные студентами задачи|Предложенные студентами задачи]]
 
 
<latex>
 
<latex>
 
Дано n ключей и n замков. Все ключи и все замки различны между собой, а каждый ключ подходит к единственному замку. Ключи (и замочные скважины) упорядочены по величине, но визуально отличия неразличимы. На каждом шаге можно попытаться вставить конкретный ключ в конкретный замок и заключить, что он подходит или больше, или меньше искомого. Постройте вероятностный алгоритм подбора ключей, требующий в среднем o( $n^2$ ) шагов
 
Дано n ключей и n замков. Все ключи и все замки различны между собой, а каждый ключ подходит к единственному замку. Ключи (и замочные скважины) упорядочены по величине, но визуально отличия неразличимы. На каждом шаге можно попытаться вставить конкретный ключ в конкретный замок и заключить, что он подходит или больше, или меньше искомого. Постройте вероятностный алгоритм подбора ключей, требующий в среднем o( $n^2$ ) шагов
Строка 6: Строка 5:
 
Комментарий. Очевидно, что прямой перебор подходящих пар ключей и замков требует квадратичного числа шагов. Удивительным кажется то, что для этой задачи построен
 
Комментарий. Очевидно, что прямой перебор подходящих пар ключей и замков требует квадратичного числа шагов. Удивительным кажется то, что для этой задачи построен
 
детерминированный o( $n^2$ )-алгоритм. Он очень хитрый.
 
детерминированный o( $n^2$ )-алгоритм. Он очень хитрый.
 +
</latex>
 +
[[Category:Решенные задачи]]

Версия 11:36, 20 мая 2015