70
правок
Изменения
Нет описания правки
Рассмотрим <tex>I_j, \, j > 0</tex>.
# При включении ситуаций по правилу <tex>(1)</tex> необходимо лишь просмотреть предыдущий список и для каждого его элемента выполнить константное число операций.
# Если применяется правило Из леммы 2 следует, что любая ситуация, рассматриваемая в правиле <tex>(2)</tex>, то должна быть добавлена (так как она удовлетворяет условию и ее еще нет в некотором списке ). Кроме того, так как по нетерминалу можно за <tex>I_kO(1)</tex> для <tex>k \le j</tex> надо просмотреть получить список ситуаций, удовлетворяющих условию, то все ситуации, содержащие итерации внутри цикла <tex>"\cdot B"</tex> для некоторого конкретного <tex>B(*)</tex>будут приводить к добавлению в список новых ситуаций. Для каждой такой Поэтому затрачиваемое время можно отнести на счет добавляемых ситуаций (на каждую из них будет затрачено константное время), а не на счет ситуации , рассматриваемой в цикле <tex>I_j(*)</tex> включается другая ситуация, и это время относится не к рассматриваемой ситуации, а к включаемой. Кроме того, так как по второй лемме для каждой ситуации предпринимается только одна попытка включить ее в список, то не нужно тратить время на проверку того, что включаемая ситуация уже есть в списке.
# Так как грамматика фиксирована, то при применении правила <tex>(3)</tex> при рассмотрении любой ситуации количество включаемых ситуаций не превосходит некоторой константы, поэтому для каждой рассмотренной ситуации будет выполнено <tex>O(1)</tex> операций.
Таким образом, на каждую ситуацию в каждом списке тратится <tex>O(1)</tex> операций. Тогда, учитывая лемму 1, получаем, что время работы алгоритма составляет <tex>O(n^2)</tex>.
