54
правки
Изменения
→Сложность алгоритма
Пусть, <tex>n</tex> - длина входной строки, а <tex>m</tex> - количество правил вывода в грамматике.
Обработка правил вида <tex>A \Rightarrow a_i</tex> выполняется за <tex>O(nm)</tex>.
Проход по всем подстрокам выполняется за <tex>O(n^2)</tex>. В обработке подстроки присутствует цикл по всем правилам вывода и по всем разбиениям на две подстроки, следовательно обработка работает за <tex>O(nm)</tex>. В итоге - <tex>O(n^3 m)</tex>.
Следовательно, общее время работы алгоритма - <tex>O(n^3 m)</tex>. Кроме того, алгоритму требуется память (на массив <tex>d</tex>) объемом <tex>O(n^2 m)</tex>.
=== Псевдокод ===
