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

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

Текущая версия на 06:50, 4 мая 2023