Yuval이 제안한 트레이드 오프가 필요하지 않습니다. Dan Hirschberg가 먼저 설명한 동적 프로그래밍과 분할 및 정복의 혼합을 사용하여 시간과 공간에서 전체 최적 편집 시퀀스를 계산할 수 있습니다 . ( 최대 공통 서브 시퀀스를 계산하기위한 선형 공간 알고리즘. Commun. ACM 18 (6) : 341-343, 1975.)O(nm)

$O(nm)$

$O(nm)$O(n+m)

$O(n+m)$

$O(n+m)$

직관적으로 Hirschberg의 아이디어는 최적의 편집 시퀀스를 통해 절반의 단일 편집 작업을 계산 한 다음 시퀀스의 두 절반을 재귀 적으로 계산하는 것입니다. 최적 편집 순서를 메모 테이블의 한 모서리에서 다른 모서리로의 경로로 생각하면이 경로가 테이블의 중간 행을 교차하는 위치를 기록하도록 수정 된 반복이 필요합니다. 작동하는 한 가지 재발은 다음과 같습니다.

$$Half(i,j) = \begin{cases} \infty & \text{if $i<m/2$}\\ j &#038; \text{if $i=m/2$}\\ Half(i-1,j) &#038; \text{if $i>m/2$ and $Edit(i,j) = Edit(i-1,j)+1$}\\ Half(i,j-1) & \text{if $i>m/2$ and $Edit(i,j) = Edit(i,j-1)+1$}\\ Half(i-1,j-1) & \text{otherwise} \end{cases}$$

의 값은 시간을 사용하여 편집 거리 테이블 와 동시에 계산 될 수 있습니다 . 메모 테이블의 각 행은 위의 행에만 의존하므로 및 모두 계산 하려면 공간 만 있으면됩니다 .Half(i,j)

$Half(i,j)$

$Half(i,j)$Edit(i,j)

$Edit(i,j)$

$Edit(i,j)$O(mn)

$O(mn)$

$O(mn)$Edit(m,n)

$Edit(m,n)$

$Edit(m,n)$Half(m,n)

$Half(m,n)$

$Half(m,n)$O(m+n)

$O(m+n)$

$O(m+n)$

마지막으로 입력 문자열 을 으로 변환하는 최적의 편집 시퀀스 는 를 다음에 을 변환 최적의 서열이 이어진다 . 이 두 하위 시퀀스를 재귀 적으로 계산하면 전체 실행 시간은 다음 반복에 따릅니다.

임을 증명하는 것은 어렵지 않습니다A[1..m]

$A[\mathrm{1..}m]$

$A[1..m]$B[1..n]

$B[\mathrm{1..}n]$

$B[1..n]$A[1..m/2]

$A[1..m/2]$

$A[1 .. m/2]$B[1..Half(m,n)]

$B[1..Half(m,n)]$

$B[1 .. Half(m, n)]$A[m/2+1..m]

$A[m/2+1..m]$

$A[m/2 + 1 .. m]$B[Half(m,n)+1..n]

$B[Half(m,n)+1..n]$

$B[Half(m, n) + 1 .. n]$

$$T(m,n) = \begin{cases} O(n) & \text{if $m\le 1$}\\ O(m) & \text{if $n\le 1$}\\ O(mn) + \max_h \left( T(m/2,h) + T (m/2, n−h)\right) & \text{otherwise} \end{cases}$$ T(m,n)=O(mn)

$T(m,n)=O(mn)$

$T(m,n) = O(mn)$. 마찬가지로, 한 번에 하나의 동적 프로그래밍 패스를위한 공간 만 필요하므로 총 공간 한계는 여전히 입니다. 재귀 스택을위한 공간은 무시할 수 있습니다.O(m+n)

$O(m+n)$

$O(m+n)$

---

답변