Изменения

Необходимо вычислить Обработка правил вида <tex>n^2</tex> булевых величин. На каждую требуется затратить <tex>n A \cdot |P_A|rightarrow w[i]</tex> операций, где <tex>|P_A|</tex> – количество правил. Суммируя по всем правилам получаем конечную сложность в шаге 1 выполняется за <tex>O \left( n^3 \cdot |\Gamma| \right)</tex>.

Алгоритму требуется Проход по всем подстрокам выполняется за <tex>O(n^2 \cdot |N|)</tex> памяти. В обработке подстроки присутствует цикл по всем правилам вывода и по всем разбиениям на две подстроки, где следовательно обработка работает за <tex>O(n \cdot |N\Gamma|)</tex> — количество нетерминалов грамматики.***Пусть, В итоге получаем конечную сложность <tex>O(n^3 \cdot |\Gamma|)</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\cdot |N|)</tex>. Недостаток алгоритма заключается в том, что изначально грамматику необходимо привести к НФХгде <tex>|N|</tex> - количество [[Формальные_грамматики#Определения|нетерминалов]] грамматики.