Нет необходимости в компромиссе, который предлагает Ювал. Вся оптимальная последовательность редактирования может быть вычислена во времени и в пространстве , используя смесь динамического программирования и «разделяй и властвуй», впервые описанную Дэном Хиршбергом. ( Алгоритм линейного пространства для вычисления максимальных общих подпоследовательностей. Commun. ACM 18 (6): 341–343, 1975.)O ( n + m )O ( n m )O ( n + m )
Интуитивно понятно, что идея Хиршберга состоит в том, чтобы вычислить одну операцию редактирования в середине оптимальной последовательности редактирования, а затем рекурсивно вычислить две половины последовательности. Если мы рассматриваем оптимальную последовательность редактирования как путь от одного угла таблицы памятки к другому, нам понадобится измененное повторение, чтобы записать, где этот путь пересекает среднюю строку таблицы. Одно повторение, которое работает, является следующим:
ЧАСа л ф( i , j ) = ⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪∞JЧАСа л ф( i - 1 , j )ЧАСа л ф( i , j - 1 )ЧАСа л ф( i - 1 , j - 1 )если я < м / 2если я = м / 2если я > м / 2 и Еdi t ( i , j ) = Edi t ( i - 1 , j ) + 1если я > м / 2 и Еdi t ( i , j ) = Edi t ( i , j - 1 ) + 1в противном случае
Значения могут быть вычислены одновременно с таблицей расстояний редактирования с использованием времени . Поскольку каждая строка таблицы памятки зависит только от строки над ней, для вычисления как и требуется только место.E d i t ( i , j ) O ( m n ) E d i t ( m , n )ЧАСа л ф( я , j )Еdя т ( я , J )O ( м н )Еdя т ( м , н )O ( m + n )ЧАСа л ф( м , н )O ( m + n )
Наконец, оптимальная последовательность редактирования, преобразующая входные строки в состоит из оптимальных последовательностей, преобразующих в последующей оптимальной последовательностью, преобразующей в . Если мы вычисляем эти две подпоследовательности рекурсивно, общее время выполнения подчиняется следующему повторению:
Нетрудно доказать, чтоA [ 1 .. м ]B [ 1 .. n ]A [ 1 . , м / 2 ]Б [ 1 . , ЧАСа л ф( м , н ) ]А [ м / 2 + 1 . , м ]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), Точно так же, поскольку нам требуется только пространство для одного прохода динамического программирования за один раз, общая граница пространства по-прежнему равна . (Пространство для стека рекурсии незначительно.)
O(m+n)
Алгоритм, который вы описываете, который работает в пространстве фактически восстанавливает окончательное редактирование и состояние непосредственно перед финальным редактированием. Таким образом, если вы запустите этот алгоритм раз, вы сможете восстановить всю последовательность редактирования за счет увеличения времени выполнения. В общем, существует компромисс между временем и пространством, который контролируется количеством строк, которые вы сохраняете в данный момент. Двумя крайними точками этого компромисса являются пространство и пространство , и между ними произведение времени и пространства является постоянным (вплоть до больших 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)
источник