Бюрократы, editor, Администраторы
422
правки
Изменения
→Время работы для однозначной грамматики: — упростил первый случай
Рассмотрим <tex>I_j, \, j > 0</tex>.
# При включении ситуации ситуаций по правилу <tex>(1)</tex> исследуется <tex>a_j</tex> и необходимо лишь просмотреть предыдущий список. Для каждой ситуации из <tex>I_{j-1}</tex> с символом <tex>a_j</tex>, расположенным справа от точки, в <tex>I_j</tex> включается некоторая ситуация. Так как список в <tex>I_{j-1}</tex> можно найти за <tex>O(1)</tex> по символу <tex>a_j</tex>, то на включение каждой ситуации в <tex>I_j</tex> будет потрачено <tex>O(1)</tex> и для каждого его элемента выполнить константное число операций.
# Если применяется правило <tex>(2)</tex>, то в некотором списке <tex>I_k</tex> для <tex>k \le j</tex> надо просмотреть все ситуации, содержащие <tex>"\cdot B"</tex> для некоторого конкретного <tex>B</tex>. Для каждой такой ситуации в <tex>I_j</tex> включается другая ситуация, и это время относится не к рассматриваемой ситуации, а к включаемой. Кроме того, так как по второй лемме для каждой ситуации предпринимается только одна попытка включить ее в список, то не нужно тратить время на проверку того, что включаемая ситуация уже есть в списке.
# Так как грамматика фиксирована, то при применении правила <tex>(3)</tex> при рассмотрении любой ситуации количество включаемых ситуаций не превосходит некоторой константы, поэтому на рассматриваемую ситуацию будет потрачено <tex>O(1)</tex> операций.
