크기
n1과 의 두 개의 스트링이 주어지면
n2, 표준 레 벤슈 테인 편집 거리 계산은 시간 복잡도
O(n1n2)와 공간 복잡도 가진 동적 알고리즘에 의해 계산됩니다
O(n1n2). (일부 개선 편집 거리의 함수로 만들 수 있습니다
d, 그러나 우리는 아무런 가정도하지 않습니다
dO(max(n1,n2))
그러나 최적의 편집 스크립트를 실제로 편집하려면 실행 시간을 희생하여 메모리 사용량 보다 더 나은 작업을 수행 할 수 있습니까?
O(n1n2)답변
Yuval이 제안한 트레이드 오프가 필요하지 않습니다. Dan Hirschberg가 먼저 설명한 동적 프로그래밍과 분할 및 정복의 혼합을 사용하여 시간과 공간에서 전체 최적 편집 시퀀스를 계산할 수 있습니다 . ( 최대 공통 서브 시퀀스를 계산하기위한 선형 공간 알고리즘. Commun. ACM 18 (6) : 341-343, 1975.)
O(nm)O(n+m)
직관적으로 Hirschberg의 아이디어는 최적의 편집 시퀀스를 통해 절반의 단일 편집 작업을 계산 한 다음 시퀀스의 두 절반을 재귀 적으로 계산하는 것입니다. 최적 편집 순서를 메모 테이블의 한 모서리에서 다른 모서리로의 경로로 생각하면이 경로가 테이블의 중간 행을 교차하는 위치를 기록하도록 수정 된 반복이 필요합니다. 작동하는 한 가지 재발은 다음과 같습니다.
의 값은 시간을 사용하여 편집 거리 테이블 와 동시에 계산 될 수 있습니다 . 메모 테이블의 각 행은 위의 행에만 의존하므로 및 모두 계산 하려면 공간 만 있으면됩니다 .
Half(i,j)Edit(i,j)
O(mn)
Edit(m,n)
Half(m,n)
O(m+n)
마지막으로 입력 문자열 을 으로 변환하는 최적의 편집 시퀀스 는 를 다음에 을 변환 최적의 서열이 이어진다 . 이 두 하위 시퀀스를 재귀 적으로 계산하면 전체 실행 시간은 다음 반복에 따릅니다.
임을 증명하는 것은 어렵지 않습니다
A[1..m]B[1..n]
A[1..m/2]
B[1..Half(m,n)]
A[m/2+1..m]
B[Half(m,n)+1..n]
T(m,n)=O(mn)
. 마찬가지로, 한 번에 하나의 동적 프로그래밍 패스를위한 공간 만 필요하므로 총 공간 한계는 여전히 입니다. 재귀 스택을위한 공간은 무시할 수 있습니다.
O(m+n)
답변
공간에서 실행되는 알고리즘은 실제로 최종 편집 및 최종 편집 직전의 상태를 복구합니다. 따라서이 알고리즘을 번 실행하면 런타임을 늘리는 대신 전체 편집 시퀀스를 복구 할 수 있습니다. 일반적으로 시간 공간 상충 관계는 시간에 유지하는 행 수에 의해 제어됩니다. 이 절충점의 두 가지 극단적 인 점은 공간 및 공간 이며, 그 사이에서 시간과 공간의 곱은 일정합니다 (최대 O).
O(n1+n2)O(n1+n2)
O(n1n2)
O(n1+n2)