операцій в викликається процедурі, плюс власне оператор виклику (з одиничною складністю) (3, стор 108-119). З метою аналізу алгоритм (програму) зручно представляти керуючим графом (споріднене поняття - схема алгоритму). Керуючий граф будується наступним чином. Кожному оператору присвоювання або викликом процедури ставиться у відповідність вершина графа (крапка). Два послідовно записаних оператора (послідовно виконуваних) зображуються вершинами, з'єднаними стрілкою, що вказує порядок виконання (рис. 2) (3, стор 122). br/>В
Рис.2. Граф лінійної ділянки
Послідовність з декількох операторів присвоювання або викликів процедур зображується ланцюгом і називається лінійним ділянкою. Умовний оператор зображується вершиною, відповідної обчисленню умови, і двома виходять дугами з приписаними їм варіантами then, else (рис. 3). br/>
if a
В
Рис.3. Граф умовного оператора
Якщо після then записаний складений оператор (лінійний ділянка), то в керуючому графі йому відповідає ланцюг. Умовний оператор задає розгалуження в керуючому графі, що закінчується порожній вершиною (без операцій), поміченої крапкою з комою. Якщо в операторі частина else відсутнє, то нижня гілка включає порожню вершину. Подібний фрагмент в керуючому графі породжує оператор вибору case, але тільки розгалуження може бути на більше число гілок і виходять дуги позначаються відповідними константами (рис. 4). br/>В
Рис.4. Граф оператора розгалуження
Оператори циклу (малюнок 5) зображуються в керуючому графі замкнутої послідовністю вершин (циклом).
В
Рис.5. Графи операторів циклу
Крім цього в керуючому графі вводиться одна початкова вершина і одна або декілька заключних вершин. Кожній вершині графа пріпішем число - кількість операцій, які необхідно виконати для виконання оператора програми, пов'язаного з цією вершиною. Це число назвемо вагою вершини. Вага порожній, початкової і заключних вершин дорівнює нулю. Якщо з вершини виходить дві або більше дуги, то кожній з них пріпішем умова, при виконанні якого обчислювальний процес піде в цьому напрямку. Ці умови будемо називати позначками дуг. Таким чином, керуючий граф програми являє собою спрямований зважений граф. p> Необхідно розглянути наступні кілька випадків (6, стор 172-178):
Керуючий граф являє собою лінійний ділянку. Складність дорівнює сумі ваг вершин, що належать лінійному ділянці, і є константою, якщо на ділянці немає вершин - викликів процедур. Якщо такі вершини є, то їх вага дорівнює функціям складності відповідних процедур. p> Керуючий граф містить розгалуження, але не містить циклів. Це означає, що обчислювальний процес в залежності від вихідних даних може попрямувати за однією з кінцевого числа гілок, що починаються в початковій вершині і закінчуються в одній з кінцевих вершин. Розрахунок функції складності залежить від того, розглядається найгірший випадок або середній випад...
