й високого порядку. Тому даний спосіб передбачає використання ЕОМ для виконання необхідних розрахунків. br/>
Мережевий метод оцінки трудомісткості алгоритмів
Кількість обчислень, вироблених при розрахунках трудомісткості алгоритмів, можна значно скоротити, якщо використовувати мережевий підхід до аналізу трудомісткості алгоритмів. Він дозволяє отримувати середню, мінімальну і максимальну трудомісткість. p align="justify"> Суть мережевого підходу полягає у виділенні шляхів на графі алгоритму, відповідних мінімальної, середньої та максимальної трудомісткості послідовності операторів. Ці шляхи можуть бути виділені тільки на графах, що не містять циклів. З цієї причини методика мережевого підходу починається з аналізу трудомісткості алгоритмів, що не містять цикли. Потім розглядається прийом виключення циклів з графа алгоритму шляхом заміни їх операторами з еквівалентною трудомісткістю. Цей прийом дозволяє поширити мережевий підхід на будь-які алгоритми, в тому числі що містять будь-яку кількість циклів. br/>
Оцінка середньої трудомісткості алгоритмів
Алгоритм будемо представляти у вигляді графа, що складається з До операторних вершин і має єдину кінцеву вершину з номером К = К 1; дуги графа відзначені вірогідністю переходів Pij. Кожній вершині графа поставлено у відповідність середнє значення трудомісткості ki або lj. Задача оцінки трудомісткості алгоритму зводиться до визначення середнього числа n1, n2, ..., nk звернень до операторів за один прогін алгоритму. p align="justify"> Для застосування мережевого підходу до оцінки трудомісткості алгоритму, що не містить цикли, вершини графа алгоритму повинні бути пронумеровані в порядку їх слідування, тобто так, щоб будь-яка вершина мала номер, більший будь-якого номера попередніх їй вершин. Нумерація проводиться наступним чином. Початковою вершині присвоюється номер 0. Черговий номер i = 1,2, ... присвоюється вершині, до якої входять дуги від вже пронумерованих вершин з номерами, меншими i. При цьому будь-яким двом вершинам повинні відповідати різні номери. Такий порядок нумерації є результативним для будь-якого графа без циклів. Причому кінцева вершина графа буде мати максимальний номер К. Приклад коректної нумерації вершин графа (*):
Оскільки граф не містить циклів, то при прогоні алгоритму вершина 1 буде виконана точно один раз, тобто n1 = 1. Середнє число влучень обчислювального процесу в вершину визначається виразом:
В
де Рji - ймовірність переходу з вершини j у вершину i.
При встановленому порядку нумерації вершин на момент обчислення ni значення n1, n2,., ni-1 вже визначені. Тому обчислення значення ni зводиться до підсумовування творів, причому оскільки Pij = 0 для всіх j0, то підсумовування слід проводити тільки для j Визначимо середнє число звернень n1, n2,., nk до операто...
