70
правок
Изменения
Нет описания правки
Рассмотрим <tex>I_j, \, j > 0</tex>.
# При включении ситуаций по правилу <tex>(1)</tex> необходимо лишь просмотреть предыдущий список и для каждого его элемента выполнить константное число операций.
# Из леммы 2 следует, что любая ситуация, рассматриваемая в правиле Рассмотрим правило <tex>(2)</tex>, должна быть добавлена (так как она удовлетворяет условию и ее еще нет в списке). Кроме тогоМожно считать, так как по нетерминалу можно за что внутри цикла <tex>O(1*)</tex> получить рассматриваются те и только те ситуации, которые удовлетворяют условию (так как список таких ситуаций, удовлетворяющих условию, то все итерации внутри цикла можно по нетерминалу получить за <tex>O(*1)</tex> будут приводить к добавлению ). Тогда каждая такая ситуация будет добавлена в список новых ситуацийи, исходя из леммы 2, попытка добавления будет единственной. Тогда, А так как по лемме 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(j)</tex> операций. Тогда время работы алгоритма составляет <tex>O(n^2)</tex>.
