вибираним можливо найбільш близьким до кореня. Закінчення процесу відбувається, коли корінь виявляється знайденим із заданою точністю e за допомогою, наприклад, наступної функції. br/>
function P_root (p: integer; x, z0, epsilon: real): real;: integer;, z: real;: = z0;: = z;
у: = old; i: = 2 to p - 1 do у: = y * old;: = (p - l) * old/p + x/(p * y); abs (z - old)
end;
З теорії чисельних методів відомо, що необхідна кількість n ітерацій для досягнення заданої точності має порядок. Цей процес сходиться (закінчується) дуже швидко: вже при 5 ітераціях досягається точність вище 10-9. p> У загальному випадку умова в операторі while або в операторі repeat ділить область комбінацій вихідних і проміжних даних, тобто область можливих станів програми на момент початку виконання оператора циклу на дві частини: для першої умова виконується, а для другої - ні. Якщо початковий стан належить першій підобласті (для while) або другий підобласті (для repeat), то з кожним виконанням тіла циклу стан (як точка в просторі станів) буде переміщатися за деякою траєкторії, яка від операцій, заданих в тілі, до тих пір, поки не перетне межу області. Саме кількість кроків до перетину кордону і визначає складність цієї ділянки програми. br/>
5. Аналіз складності рекурсивних алгоритмів
Розглянемо спочатку випадок прямої рекурсії з єдиним (поза будь-якого циклу) рекурсивним викликом в тілі процедури. Прикладом такого алгоритму є алгоритм Евкліда обчислення найбільшого загального дільника. Текст рекурсивної процедури з вектором вихідних даних X містить виклик цієї ж процедури із зміненим по деякому правилу вектором вихідних даних Y = f (X). Крім цього, в тексті міститься деякий нерекурсівние обчислення h (X) і операції порівняння c (Х, S) значення X зі значенням S, при якому рекурсивний процес повинен закінчуватися. Позначимо "точне" (а не верхню межу або середнє) значення складності при вхідних даних X через Т a (X). Тоді
Т a (X) = Т a (Y) + Th (X) + Tc (X, S), або Т a (X) = Т a (АХ)) + Tf (X) + Th (X) + Tc ( X, S).
Друге співвідношення являє собою рекурентне рівняння для визначення значень невідомої функції Т a (X) через відомі значення f (A ), Tf (X), Th (X), Tc (X, S). Крім цього, є початкова умова T a (S) = Ts (S) з відомою функцією складності обчислення (нерекурсівние) значення S . Таким чином, є система:
Т a
