53
правки
Изменения
Нет описания правки
* '''Завершение''': После окончания работы ответ содержится в ячейке <tex>a_{S, 1, n}</tex>, где <tex>n = |w|</tex>.
== Время работы Оценка сложности ==Расчёт вспомогательной динамики занимает <tex>O \left( n^3 \cdot |\Gamma| \cdot M \right)</tex> времени, основной динамики — <tex>O \left( n^2 \cdot |\Gamma| \right)</tex>. Итоговая временная сложность алгоритма равна <tex>O \left( n^3 \cdot |\Gamma| \cdot M \right)</tex>. Алгоритму требуется <tex>O(n^2 \cdot |\Gamma| \cdot M)</tex> памяти.
