70
правок
Изменения
Нет описания правки
'''exit''' <tex>0</tex>
'''return''' <tex>memo[f(\phi)]</tex>
[[Файл:Berman-Fortune.png|thumb|right|Двоичное дерево, получающееся в результате рекурсивных вызовов модифицированной программы. Красным и желтым помечены узлы, в которых происходит обращение к элементу ''memo[j]''. В красных узлах условие ''(1)'' ложно, в желтых {{---}} истинно.]]
Рассмотрим двоичное дерево, получающееся в результате рекурсивных вызовов данной программы.
Рассмотрим произвольный элемент <tex>memo[ij]</tex>. Найдем, сколько раз условие <tex>(1)</tex> в ходе выполнения программы является ложным при обращении к элементу <tex>memo[ij]</tex>. Найдем в дереве такой узел, в котором есть обращение к <tex>memo[ij]</tex>, а в его поддереве обращений к этому элементу нет, причем <tex>memo[ij] = -1</tex>. До этого момента количество обращений к <tex>memo[ij]</tex> не превышает глубины найденного узла, что не превосходит высоты дерева, что не превосходит некоторого полинома <tex>p'(n)</tex>. После этого момента условие <tex>(1)</tex> будет принимать истинное значение при обращении к <tex>memo[ij]</tex>. Значит, в ходе выполнения программы условие <tex>(1)</tex> является ложным при обращении к <tex>memo[ij]</tex> не более <tex>p'(n)</tex> раз.
Так как всего в <tex>memo</tex> не более <tex>r(n)</tex> элементов, то суммарно за все время выполнения программы условие <tex>(1)</tex> принимает ложное значение не более <tex>p''(n) = r(n) \cdot p'(n)</tex> раз, то есть <tex>p''</tex> {{---}} полином. Отсюда следует, что присваивание <tex>(2)</tex> выполняется не более <tex>p''(n)</tex> раз, а значит в дереве не более <tex>p''(n)</tex> внутренних вершин. Значит всего в дереве не более <tex>2 \cdot p''(n) + 1</tex> вершин, то есть данная программа работает за полиномиальное время.
