Изменения
→Оценка сложности
Обработки правил вида <tex>A \rightarrow w[i]</tex>, <tex>A \rightarrow \varepsilon</tex> и нахождение <tex>h\left[A \rightarrow \alpha, i, i, 0\right]</tex> выполняются за <tex>O(n \cdot |\Gamma|)</tex>.
Время одного перехода вспомогательной динамики <tex>O(n)</tex>, суммарное количество число состояний <tex>O(n^2 \cdot |\Gamma| \cdot M)</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> памяти.
== См. также ==
