문자 교체 단어를 생성하는 데 큰 시간이 필요합니까?

Question

'cook'과 같은 단어가 있다고 가정 해보자. 각 단어를 다른 모든 문자로 바꾸면 그 단어에서 가능한 모든 단어의 그래프를 생성하려고합니다. 중요한 제한 사항 : 글자 모음이 단어인지 사전에 요청할 수 있지만 이는 사전에 대한 인터페이스의 한계입니다. 사전에 n 문자로 된 모든 단어를 요청할 수는 없습니다. 그래서

          cook 
           /  |  \ 
           aook  ...  zook 
          /| \   /| \ 
          aaok ... azok  zaok ... zzok 

그리고를 다음과 같이 내가 이것을 상상

는 DAG를 생성하는 재귀 알고리즘 될 것이다. 분명히 실제로 이러한 순열 중 많은 수가 실제 단어가 아니라고 거부 될 것이지만 결국에는 생성 될 수있는 모든 '단어'를 포함하는 DAG를 갖게됩니다. 그래프의 높이는 입력 단어의 길이에 1을 더한 값이됩니다.

최악의 경우, 각 순열은 단어입니다. 첫 번째 레벨은 1 단어, 두 번째 레벨은 25, 다음 레벨 (25 * 25) 등이 있습니다. 따라서 n이 단어의 길이라면, 알고리즘이 최악의 경우의 시간 복잡도가 25^n이고 최악의 경우의 저장 복잡성이 25^n이라는 것을 의미한다고 생각하면 정확합니까?

Answer 1

아마도 나무로 보는 것이 아니라 그래프로 보는 것이 좋습니다.

n을 입력으로 사용하면 단어의 길이를 알 수 있습니다.

W을 길이가 $ n $ 인 모든 (의미있는) 단어라고합시다.

다음과 같이 간단한 그래프 G을 만듭니다. G의 꼭지점은 W입니다. 두 단어 w1과 w2은 한 문자 씩 다른 경우에만 연결하는 가장자리가 있습니다. 단어 W에서 w을 감안할 때

는, 그래프 G에 w의 연결 구성 요소를 찾을 수 :

그런 다음 당신이하고 싶은 기능은 다음이다.

이것은 일반적으로 depth-first search (DFS) 또는 breadth-first search (BFS)으로 수행됩니다. 알고리즘은 일종의 BFS입니다 (그러나 정확하지는 않습니다 : 한 자리가 대체 된 단어뿐만 아니라 한 단어의 모든 이웃을 생성 할 때마다).

우리 $을 가정 할 수 있기 때문에 n은 또한 메모리의 동일한 크기를 가져야

단 (매우 큰 큰 O 상수와 있지만) 작은 $ 시간 복잡도는 이론적 결과의 크기에 선형 , 어떤 단어가 이미 확인되었는지 기억합니다.

Answer 2

사전에서 찾을 수있는 단어 만 생성하는 경우 시간 복잡도는 사전 크기에 의해 제한되므로 O(min(|D|, 25^n))이어야합니다.