10
правок
Изменения
м
→Затраты на память
Проанализируем затраты на память. Три глобальные последовательности (две исходные и одна для ответа), к которым мы обращаемся внутри алгоритма, требуют <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>
== См. также ==
