Вы находитесь в случайном вагоне зацикленного поезда (последний вагон соединен с первым). В каждом вагоне случайным образом горит или не горит свет. Вы можете совершать следующие действия: Перейти в следующий вагон Перейти в предыдущий вагон Узнать, горит ли в нынешнем вагоне свет Переключить свет в нынешнем вагоне Придумайте такой алгоритм определения количества вагонов в поезде, чтобы в худшем случае он совершал минимальное количество действий среди других таких алгоритмов. Какова алгоритмическая сложность такого алгоритма в нотации O-большое, если N - количество вагонов в поезде? O(1) O(log(N)) O(N) O(N^2) O(2^N) O(N!)

О(log(N))

Алгоритм будет заключаться в том, чтобы каждый раз действовать в зависимости от того, горит ли свет в текущем вагоне, и двигаться в направлении, где свет горит. Таким образом, на каждом шаге мы будем уменьшать количество вагонов, которые нужно проверить вдоль поезда, в два раза.