На этом шаге мы рассмотрим построение функции сложности по управляющему графу, содержащему циклы
while или repeat.
Циклы while и repeat анализировать сложнее, чем оператор for, так как количество исполнений тела цикла зависит от истинности или ложности условия и, может быть, достаточно сложных изменений в теле цикла значений переменных, входящих в состав условия.
Рассмотрим в качестве примера вычисление методом Ньютона (имеется в виду вычисление вещественного значения корня). Задача сводится к нахождению корня уравнения x(1/p) - z = 0, который, в свою очередь, отыскивается с помощью итерационного процесса
начинающегося некоторым начальным значением z0, выбираемым возможно наиболее близким к корню. Окончание процесса происходит, когда корень оказывается найденным с заданной точностью ε с помощью, например, следующей функции.
function P_root( p: integer; x, z0, epsilon: real ): real; var i: integer; old, z: real; begin z := z0; repeat old := z; у := old; for i:= 2 to p - 1 do у:= y*old; z := (p - l)*old/p + x/ (p*y); until abs( z - old ) < epsilon; end;
Из теории численных методов известно, что требуемое количество n итераций для достижения заданной точности имеет порядок . Этот процесс сходится (заканчивается) очень быстро: уже при 5 итерациях достигается точность выше 10-9.
В общем случае условие в операторе while или в операторе repeat делит область комбинаций исходных и промежуточных данных, т.е. область возможных состояний программы на момент начала исполнения оператора цикла на две части: для первой условие выполняется, а для второй - нет. Если начальное состояние принадлежит первой подобласти (для while) или второй подобласти (для repeat), то с каждым выполнением тела цикла состояние (как точка в пространстве состояний) будет перемещаться по некоторой траектории, зависящей от операций, заданных в теле, до тех пор, пока не пересечет границу области. Именно количество шагов до пересечения границы и определяет сложность этого участка программы.
На следующем шаге мы рассмотрим анализ сложности рекурсивных алгоритмов.