D1 і D2, а потім кожна з них ділиться пунктирними лініями на підобласті D3, D4 і D5, D6. br/>
В
Рис.6. Керуючий граф і розбиття області даних
Кожна підобласть, не розділена на більш дрібні частини, відповідає однієї гілки в керуючому графі. Позначимо всі такі області di. Тоді, вважаючи всі комбінації вихідних даних рівноімовірними, можемо оцінити частоту виконання i-ї гілки як відношення потужності безлічі di до потужності безлічі D, pi = | di |/| D |. Якщо i-я гілка має вагу li то складність програми можна оцінити величиною
, де k - кількість гілок.
Приклад 3. Той же граф, що й у прикладі 1. Умова в операторі if має вигляд (x <0,5), де x - вхідна змінна, значення якої належать інтервалу [0,1]. Якщо детальнішої інформації про вхідний змінної немає, то можна припускати, що ймовірність отримати на вході значення xГЋ [0, 0,5] дорівнює ймовірності отримати x ГЋ [0,5, 1] ​​і, значить та і інша ймовірності рівні 0,5 . Отже, і ймовірності гілок однакові; середня складність дорівнює 28 (1/2) + 31 (1/2) = 29,5. p> Приклад 4 (об'єднання умов прикладів 2 і 3). Середня складність дорівнює 28 (1/2) + (2V + 24) (1/2) = V + 26. p> Керуючий граф містить цикл, породжений оператором for. Якщо вирази, що визначають початкове і кінцеве значення параметра циклу - константи, то підраховуємо, скільки разів буде виконуватися тіло циклу і множимо на цей коефіцієнт вага тіла циклу. Якщо вираження залежать від вихідних даних, то оцінюємо значення різниці цих виразів в гіршому або середньому випадках. p> Приклад 5. Процедура містить цикл
for i: = 1 to x do
<тіло циклу>,
де x - вхідна змінна, xГЋ [1,100]. Тіло циклу виконується x раз, найгірший випадок реалізується при x = 100. Якщо припустити рівноймовірно різних значень x, то середнє кількість виконань тіла циклу дорівнює (1/100) (1 +2 +3 + ... +100) = 50,5. p> Приклад 6. Процедура містить вкладені цикли:
for i: = 1 to x doj: = i to x do
<тіло циклу>;
вхідна змінна xГЋ [1, 5]. Тіло циклу виконується x + (x-1) + (х-2) + ... + 1 = x (х +1)/2 разів. Верхня межа складності = max = (x (х +1)/2) = 13. Середнє значення складності підрахувати дещо важче. Знову покладемо, що всі 5 можливих значень x рівноймовірні. Тоді середнє значення складності одно:
В
Керуючий граф містить цикл, породжений операторами while або repeat. Цикли while і repeat аналізувати складніше, ніж оператор for, так як кількість виконань тіла циклу залежить від істинності чи хибності умови і, може бути, досить складних змін у тілі циклу з начен змінних, що входять до складу умови.
Розглянемо як приклад (4, стор 334) обчислення методом Ньютона (мається на увазі обчислення речового значення кореня). Завдання зводиться до знаходження кореня рівняння x (1/p) - z = 0, який, у свою чергу, відшукується за допомогою ітераційного процесу
В
починається деяким початковим значенням z0,...
