рів алгоритму зображеного графа (попередній малюнок)
В
Розглянемо випадок алгоритму, що містить цикли:
В
Безпосереднє застосування описаної методики до таких алгоритмів неможливо і для обчислення значень n1, n2,., nk необхідно виключити цикли, замінюючи їх операторами з еквівалентною трудомісткістю.
Для спрощення опису методу приймемо, що алгоритм складається з однотипних операторів, наприклад, тільки основних операторів. Розділимо цикли по рангах. До рангу 1 відносяться цикли, які не містять всередині себе жодного циклу, до рангу 2 - цикли, всередині яких є цикли не вище рангу 1 і так далі. Наприклад, розглянутий алгоритм містить два цикли С1 і С2 рангу 1 і один цикл С2 рангу 2. Сукупність операторів, що входять в цикл, і пов'язують їх дуг, за винятком дуги, що замикає цикл, називають тілом циклу. Тіло циклу рангу 1 є графом без циклів. Застосовуючи до цього графу раніше розглянуту методику, можна визначити значення ni для кожного з операторів, що належать тілу циклу, і, отже, трудомісткість тіла З-го циклу. p> Тут підсумовування проводиться по всіх вершин Vj, що містяться в циклі С.
Нехай відомо середнє число повторень циклу nc, яка дорівнює кількості виконань тіла циклу при одному прогоні алгоритму. Якщо ймовірність переходу по дузі, що замикає цикл, дорівнює Pkl, то nC =
У цьому випадку середня трудомісткість циклу дорівнює:
В
і цикл С можна замінити оператором з трудомісткістю kC.
Застосовуючи зазначену процедуру заміни циклів операторами до всіх циклам рангу 1, потім до циклів рангу 2 і так далі, зрештою прийдемо до графа без циклів, трудомісткість якого знаходиться вже розглянутим способом.
Визначимо трудомісткість, задану наведеним вище графом.
Покладемо, що трудомісткість всіх операторів однакова і дорівнює 1. Середнє число повторень циклів С1, С2 і С3 визначається з ймовірностей переходів, зазначених на графі, такими значеннями:
В
В
Виділимо тіла циклів С1 і С2 першого рангу:
Застосовуючи до цих графам розглянуту раніше методику, визначаємо середню трудомісткість kC1 і kC2 виконання тел цих циклів:
В
Визначаємо трудомісткість тел цих циклів:
В
Середня трудомісткість циклів С1 ИС2 обчислюється множенням отриманих значень на середнє число повторень цих циклів:
;
Замінюючи у вихідному графі цикли С1 і С2 операторами С1 і С2 з трудомісткістю kC1 і kC2, отримаємо граф:
В
Тіло циклу С3 має вигляд:
В
Визначимо трудомісткість тіла циклу С3:
В В
З урахуванням числа nC3 повторень циклу трудомісткість циклу складе:
операцій.
Замінивши цикл С3 оператором С3 з трудомісткістю kC3, отримаємо граф:
В
Трудомісткість всього алгоритму, репрезентованої цим графом, дорівнює:
операцій.
...
