Não há necessidade da troca que Yuval sugere. Toda a sequência ótima de edição pode ser calculada no tempo e no espaço , usando uma mistura de programação dinâmica e divisão e conquista descrita pela primeira vez por Dan Hirschberg. ( Um algoritmo de espaço linear para calcular as subsequências comuns máximas. Commun. ACM 18 (6): 341–343, 1975.)O ( n + m )O ( n m )O(n+m)
Intuitivamente, a ideia de Hirschberg é calcular uma única operação de edição no meio da sequência de edição ideal e, em seguida, calcular recursivamente as duas metades da sequência. Se pensarmos na sequência de edição ideal como um caminho de um canto da tabela de memorização para o outro, precisamos de uma recorrência modificada para registrar onde esse caminho cruza a linha do meio da tabela. Uma recorrência que funciona é a seguinte:
Half(i,j)=⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪∞jHalf(i−1,j)Half(i,j−1)Half(i−1,j−1)if i<m/2if i=m/2if i>m/2 and Edit(i,j)=Edit(i−1,j)+1if i>m/2 and Edit(i,j)=Edit(i,j−1)+1otherwise
Os valores de podem ser calculados ao mesmo tempo que a tabela de distâncias de edição , usando o tempo . Como cada linha da tabela de memorização depende apenas da linha acima, a computação de e requer apenas espaço .Half(i,j)Edit(i,j)O(mn)Edit(m,n)Half(m,n)O(m+n)
Finalmente, a sequência de edição ideal que transforma as seqüências de entrada em consiste nas seqüências ideais que transformam em seguido pela seqüência ótima que transforma em . Se calcularmos essas duas subsequências recursivamente, o tempo de execução geral obedecerá à seguinte recorrência:
Não é difícil provar queA[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(n)O(m)O(mn)+maxh(T(m/2,h)+T(m/2,n−h))if m≤1if n≤1otherwise
O ( m + n )T(m,n)=O(mn). Da mesma forma, como exigimos apenas espaço para uma passagem de programação dinâmica por vez, o espaço total vinculado ainda é . (O espaço para a pilha de recursão é insignificante.)
O(m+n)
O algoritmo que você descreve que é executado no espaço na verdade recupera a edição final e o estado imediatamente antes da edição final. Portanto, se você executar esse algoritmo vezes, poderá recuperar toda a sequência de edição, à custa de aumentar o tempo de execução. Em geral, há uma troca de espaço no tempo que é controlada pelo número de linhas que você retém no momento. Os dois pontos extremos dessa troca são o espaço e o espaço e, entre eles, o produto do tempo e do espaço é constante (até o grande O).O ( n 1 + n 2 ) O ( n 1 n 2 ) O ( n 1 + n 2 )O(n1+n2) O(n1+n2) O(n1n2) O(n1+n2)
fonte