418
правок
Изменения
м
→Асимптотика
Проход по всем подстрокам выполняется за <tex>O(n^2)</tex>. В обработке подстроки присутствует цикл по всем правилам вывода и по всем разбиениям на две подстроки, следовательно обработка работает за <tex>O(n \cdot |\Gamma|)</tex>. В итоге получаем конечную сложность <tex>O(n^3 \cdot |\Gamma|)</tex>.
Следовательно, общее время работы алгоритма - <tex>O(n^3 m\cdot |\Gamma|)</tex>. Кроме того, алгоритму требуется память (на массив <tex>d</tex>) объемом <tex>O(n^2 \cdot |N|)</tex>, где <tex>|N|</tex> - количество [[Формальные_грамматики#Определения|нетерминалов]] грамматики.
== См. также ==
