Похоже на проблему коммивояжера? Флуд консоль с выходом?

Question

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ Это криптографическая программа для одного из моих занятий и, возможно, личного пользования. Однако меня не оценивают.

Я уже взломал этот код, и это случайный шифр Цезера. Q PC JI UQTGF TQBMU SIX. XMGS QJ UMQJ IKGT?

Теперь, чтобы решить это вычислительно, используя словари, не будет ли это похоже на проблему коммивояжера? O (n!) Для худшего случая. Кроме того, поскольку у компьютера нет возможности узнать, правильно ли что-то, разве мне не пришлось бы выкладывать каждую конечную перестановку для проверки? Или я должен поставить какие-то нижние границы для обзора человеком? Как минимум 40% совпадений?

Answer 1

Цезарь Шифры просто принимают буквы и заменяют их на смещенные буквы s.

Итак: для каждой буквы в алфавите a,

Вы повторяете a times.

Затем для каждого из v слов в шифре вы должны пройти по d словам в словаре.

Цикл по словам, игнорирование сжатий и еще много чего, приведет к сложности O(a*v*d), а если a==26, O(v*d).Однако сложность в основном основана на том, КАК РАБОТАЕТ ВАШ СЛОВАРСКИЙ АЛГОРИТМ - O( is_sentence_valid) == O(cipher_solver)