70
правок
Изменения
Нет описания правки
Рассмотрим <tex>I_j, \, j > 0</tex>.
# При включении ситуаций по правилу <tex>(1)</tex> необходимо лишь просмотреть предыдущий список и для каждого его элемента выполнить константное число операций.
# Из леммы 2 следует, что любая ситуация, рассматриваемая в правиле <tex>(2)</tex>, должна быть добавлена (так как она удовлетворяет условию и ее еще нет в списке). Кроме того, так как по нетерминалу можно за <tex>O(1)</tex> получить список ситуаций, удовлетворяющих условию, то все итерации внутри цикла <tex>(*)</tex> будут приводить к добавлению в список новых ситуаций. Поэтому затрачиваемое время можно отнести на счет добавляемых Тогда, так как по лемме 1 в списке <tex>I_j</tex> <tex>O(j)</tex> ситуаций , то суммарно за все итерации внешнего цикла while правило <tex>(на каждую из них 2)</tex> будет затрачено константное время), а не на счет ситуации, рассматриваемой в цикле применено <tex>O(*j)</tex>раз.
# Так как грамматика фиксирована, то при применении правила <tex>(3)</tex> при рассмотрении любой ситуации количество включаемых ситуаций не превосходит некоторой константы, поэтому для каждой рассмотренной ситуации будет выполнено <tex>O(1)</tex> операций.
Таким образом, на каждую ситуацию в каждом списке тратится построение списка <tex>I_j</tex> будет потрачено <tex>O(1j)</tex> операций. Тогда, учитывая лемму 1, получаем, что время работы алгоритма составляет <tex>O(n^2)</tex>.
}}
==Литература==
*А. Ахо, Дж. Ульман. Теория синтакcического анализа, перевода и компиляции. Том 1. Синтакcический анализ.
