Изменения

|definition = Пусть имеются последовательности <tex> X = \left \langle x_1, x_2, \dots, x_m \right \rangle </tex> и <tex> Y = \left \langle y_1, y_2, \dots, y_n \right \rangle </tex>. Необходимо найти <tex>LCS(X,Y)</tex> за время <tex> O(nm) </tex> и <tex> O(\min (n, + m)) </tex> памяти.

it_max = 0-1

hirschberg(x[mid + 1 .. x.size()], y[it_max + 1 .. y.size()]) === Доказательство корректности. Асимптотика ===  Рассмотрим временные затраты алгоритма. Рекурсия представима в виде бинарного дерева высоты не более <tex> \log (m) </tex>, так как она основана на разделении первой последовательности на две равные части на каждом шаге алгоритма. Оценим время выполнения для произвольной глубины такого дерева и просуммируем результат по всем возможным значениям парметра. На глубине <tex> h </tex> находится <tex> 2^h </tex> вершин с частью последовательности <tex> x </tex> размера <tex dpi = "200"> \frac{m}{2^h} </tex> и частью <tex> y </tex> длины <tex> k_i </tex>, где сумма семейства <tex> k_i </tex> равна <tex> n </tex>. Таким образом, получаем:  <tex dpi = "200"> \text{На глубине h: } {\sum_{i = 0}^{2^h - 1}\frac{m}{2^h} k_i = \frac{m}{2^h} \sum_{i = 0}^{2^h - 1} k_i = \frac{mn}{2^h}} </tex>  <tex dpi = "200"> \text{Суммируем по всем глубинам: } {\sum_{i = 0}^{\log m}\frac{mn}{2^i} = \frac{mn}{2^h} \sum_{i = 0}^{\log m} \frac{1}{2^i} < \frac{mn}{2^i} \sum_{i = 0}^{\infty} \frac{1}{2^i} = 2mn} </tex>  <tex> \text{Итоговая асимптотика алгоритма: } O(mn) </tex>  Осталось понять, что алгоритм находит нужную подпоследовательность. Не теряя общности, будем считать, что <tex> lcs </tex> единственная, так как нам не важно какую из равных по длине подпоследовательностей выбирать. Тогда рассмотрим разделение на две части <tex>X</tex>, часть символов LCS (возможно нулевая) попадет в первую половину, оставшаяся — во вторую. Пусть <tex> x_i </tex> последний символ из LCS в первой половине, тогда наш алгоритм выберет соответствующий ему <tex> y_i </tex> в качестве точки разделения. То есть символы из <tex> y </tex>, которые связанысо второй половиной <tex> x </tex>, лежат правее <tex> y_i </tex>, в противном случае, либо <tex> y_i </tex> не состоит в паре с <tex> x_i </tex>, либо <tex> x_i </tex> не последний символ из <tex> lcs </tex> в первой половине. Заметим, что если первая половина не содержит <tex> lcs </tex>, то точки разбиения не будет, для симметричного случая со второй половиной точкой разбиения будет <tex> y_i </tex>, которая включается в первую половину. Таким образом, мы свели поиск исходной <tex> lcs </tex> к поиску двух независимых частей. Когда в <tex> X </tex> останется 1 символ, то возможны два варинта, либоон входит в <tex> lcs </tex>, либо нет, в чем мы убеждаемся линейным поиском, случай, когда последний <tex> x </tex> не входит в <tex> lcs </tex>, возникает из-за того, что на каком-то шаге, вся подпоследовательность оказалась в одной из половин <tex> X </tex>. === Затраты на память === Проанализируем затраты на память. Три глобальные последовательности (две исходные и одна для ответа), к которым мы обращаемся внутри алгоритма, требуют <tex> m + n + \min (m, n) </tex> памяти. Дополнительно на каждом шаге рекурсии вызываются 2 функции <tex> LCS </tex>, которые суммарно требуют <tex> 4k_i </tex>, где <tex> k_i </tex> — длинна части <tex> y </tex> в текущий момент, так как для нахождения <tex> LCS </tex> достаточно двух строк матрицы <tex> lcs </tex>. Вспомогательные массивы удаляются перед рекурсивным вызовом, таким образом, общие затраты равны сумме размеров массивов на одной глубине рекурсии, то есть:  <tex dpi = "200"> \text{На глубине h: } {\sum_{i = 0}^{2^h - 1} 4 k_i = 4 \sum_{i = 0}^{2^h - 1} k_i = 4n} </tex>  <tex dpi = "200"> \text{Итого: } {n + m + \min(m, n) + 4n = O(n + m)} </tex>