Бюрократы, editor, Администраторы
422
правки
Изменения
м
→Время работы для однозначной грамматики
<tex>\forall\,j: 1 \le j \le n</tex> в списке <tex>I_j</tex> находится <tex>O(j)</tex> ситуаций.
|proof=
Так как грамматика фиксирована, то <tex>\forall i</tex> количество ситуаций вида <tex>[A \rightarrow \alpha \cdot \beta, i]</tex> не больше некоторой константы. Таким образом, так как поскольку в <tex>I_j</tex> находятся ситуации, у которых <tex>0 \le i \le j</tex>, то всего в <tex>I_j</tex> будет <tex>O(j)</tex> ситуаций.
}}
{{Лемма
#Пусть <tex>k = l</tex>. Тогда <tex>\gamma \ne \delta</tex>. Тогда, так как <tex>[B \rightarrow \gamma \cdot, k] \in I_j</tex> и <tex>[B \rightarrow \delta \cdot, k] \in I_j</tex>, то <tex>\gamma \Rightarrow a_{k+1} \dots a_j</tex> и <tex>\delta \Rightarrow a_{k+1} \dots a_j</tex>, то есть <tex>a_{k+1} \dots a_j</tex> выводится двумя разными способами.
}}
{{Теорема
Таким образом, на каждую ситуацию в каждом списке тратится <tex>O(1)</tex> операций. Тогда, учитывая лемму 1, получаем, что время работы алгоритма составляет <tex>O(n^2)</tex>.
}}
==Литература==
*А. Ахо, Дж. Ульман. Теория синтакcического анализа, перевода и компиляции. Том 1. Синтакcический анализ.
