여행 세일즈맨 문제와 비슷합니까? 콘솔 출력과 함께 홍수?

Question

면책 조항 이것은 내 수업 중 하나를위한 개인용 용도의 암호화 프로그램입니다. 그러나 나는 그것에 등급 지어지지 않고있다.

나는이 코드를 이미 깨뜨 렸으며 임의의 캐서 사이퍼입니다. Q PC JI UQTGF TQBMU SIX. XMGS QJ UMQJ IKGT?

사전을 사용하여 계산적으로이 문제를 해결하려면 여행 판매원 문제와 유사하지 않습니까? 최악의 시나리오의 경우 O (n!). 또한, 컴퓨터가 무언가가 정확한지 알 수있는 방법이 없기 때문에 검토를 위해 모든 엔딩 순열을 내뱉지 않아도됩니까? 또는 인간 검토를 위해 일종의 하한을 두어야합니까? 적어도 40 % 일치와 마찬가지로?

Answer 1

시저 암호는 문자를 가져 와서 위치를 아래로 이동 한 s 문자로 바꿉니다. 그래서

: 알파벳의 각 문자, a의 경우는,

당신은 a 번 반복.

그런 다음 암호의 v 단어 각각에 대해 d 개의 사전을 사용해야합니다.

압축과 겹침을 무시한 단어의 순환은 O(a*v*d)의 복잡성을, a==26의 경우는 O(v*d) 일 것입니다. 그러나 복잡성은 근본적으로 기초가되는 알고리즘을 기반으로합니다. O(is_sentence_valid) == O(cipher_solver)