ок. p> Керуючий граф містить цикл, породжений оператором for. Якщо вирази, що визначають початкове і кінцеве значення параметра циклу суть константи, то неважко підрахувати, скільки разів буде виконуватися тіло циклу і помножити на цей коефіцієнт вага тіла циклу. Якщо вираження залежать від вихідних даних, то можна оцінити значення різниці цих виразів в гіршому або середньому випадках. p> Керуючий граф містить цикл, породжений операторами while або repeat. Цикли while і repeat можуть викликати більше ускладнень при аналізі, ніж оператор for, так як кількість виконань тіла циклу залежить від істинності чи хибності умови, а змінні, що входять до складу умови змінюються в тілі циклу, причому оцінити величину і спрямованість цієї зміни досить складно.
Керуючий граф містить розгалуженні. Для гіршого випадку потрібно обчислити вагу кожної гілки як суму ваг входять до неї вершин, після чого знайти максимальний з ваг гілок. Це і буде складністю процедури. p> Приклад 1. Керуючий граф містить 10 вершин з вагою {3, 5, 1,4, 3, 4, 6, 8, 5, 3}. Вершина 3 (вага дорівнює 1) відповідає обчисленню умови в операторі if; вершини 4, 5, 6 входять до частини then, вершини 7, 8 входять до частини else. Таким чином, є дві гілки з вагою 3 +5 +1 +4 +3 +4 +5 +3 = 28 і 3 +5 +1 +6 +8 +5 +3 = 31; складність дорівнює 31. p> Приклад 2. Той же граф, що й у прикладі 1, але вершина 8 відповідає викликом процедури, що має складність 2V + 1. У цьому випадку функція складності дорівнює max (28, 2V +24) = 24 + max (4, 2V) = 24 + 2 max (2, V). p> Для середнього випадку, крім ваги гілок, потрібно оцінити ще й частоти гілок. Під частотою гілки розуміється відношення числа виконань програми, при яких виконувалися оператори, що належать даної гілки, до загального числа виконань програми. Тоді складність програми буде обчислюватися як сума добутків ваг гілок на їх частоти. Якщо всі комбінації вихідних даних програми рівноймовірні, то частоти гілок можна оцінити таким чином: (7, стор 188)
Нехай керуючий граф містить розгалуження з умовами C1, C2, C3, ..., Cn, причому перевірка умови C1 виробляється завжди першої по ходу виконання програми. Отже, умова С1 розбиває всі гілки на дві групи: для гілок першої групи це умова істинно, а для гілок другої групи - помилково. Умова С2 розбиває групу гілок з істинним умовою С1 на дві групи, що задовольняють умовам C1 and C2 і C1 and not С2. Умова С3 породжує групи гілок, які відповідають умовам not C1 and С3 і not C1 and not С3 і т. д. Безліч D комбінацій вихідних даних також ділиться на дві частини D1 і D2 і цей поділ породжується умовою C1 навіть, якщо самі вихідні дані не входять у формулювання умови, а входять лише константи і проміжні змінні. У свою чергу, D1 ділиться на підмножини D2 і D3 відповідно з умовою C2 і так далі. На малюнку 1 зображені приклади керуючого графа програми і разбиений областей D. Три умовних оператора зображені чорними вершинами, область D ділиться спочатку суцільною лінією на підобласті ...
