10
правок
Изменения
Нет описания правки
и частью <tex> y </tex> длины <tex> k_i </tex>, где сумма семейства <tex> k_i </tex> равна <tex> n </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> k_i </tex> — длина части <tex> y </tex> в текущий момент, так как для нахождения <tex> LCS </tex> достаточно двух строк матрицы <tex> lcs </tex>. Вспомогательные массивы удаляются перед рекурсивным вызовом, таким образом, общие затраты равны сумме размеров массивов на одной глубине рекурсии, то есть:
* На глубине h: <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>
== См. также ==
