 |
Определение трудоемкости алгоритмов
|
|
|
|
Сетевой метод. Позволяет определить минимальную, максимальную и среднюю трудоемкость.
Перед расчётом производится нумерация вершин ГСА по номерам 0,1,2,...,К; где 0 и к соответственно номера начальной и конечной вершин. Затем выделяются циклы по рангам 1,2,.... Для цикла m с низшим рангом находится среднее число повторений ' 
' на один прогон алгоритма
(2.4)
где 
- вероятность перехода по дуге, замыкающей цикл по вершинам к и /. Затем определяется среднее время выполнения операторов тела цикла 
, для чего находится среднее число обращений 
к вершинам i этого тела
(2.5)
где z - множество номеров вершин, предшествующих номеру i, 
-вероятности обращений из вершин j в вершину i. После определения всех определяется
(2.6)
где R - множество номеров вершин цикла m; 
- средние времена выполнения операций в вершине i (см. (2.1 + 2.3)). Для цикла определяется среднее время выполнения
(2.7)
И цикл заменяется эквивалентным оператором со средним временем выполнения 
.
Повторяя процедуру для всех циклов последовательно по рангам и заменяя их эквивалентными операторами, в последующем находится среднее время выполнения алгоритма.
Аналогично определяется минимальное и максимальное время выполнения. Для этого находятся минимальное и максимальное время цикла с номером m последовательно по рангам с заменой их эквивалентными операторами с временами 
и 
. Здесь 
и 
- минимальное и максимальное время выполнения тела цикла m; 
и 
- минимальное и максимальное число повторений цикла.
Времена и находятся по формулам
(2.8)
Здесь 
и 
- времена выполнения операторов начальной вершины; 
и 
- минимальное и максимальное время на момент окончания выполнения операторов i -ой вершины; (j,i) - дуга из вершины j в вершину i; Dm -множество дуг; к - номер конечной вершины цикла; времена и ; выбираются по отношению ко всем вершинам j, связанными выходами с вершиной i; 
и 
- минимальное и максимальное время выполнения операторов в вершине i.
|
|
|
Трудоемкость алгоритма – это объем работы, которое необходимо выполнить. Для его реализации она может быть измерена в числе тактов, количестве команд и т.д.
Существует сетевой метод оценки трудоемкости, который основан на описании алгоритма в виде граф - схемы алгоритма (ГСА).
ГСА состоит из операторных вершин, связанных между собой дугами переходов. Вершины делятся на 3 типа (начальная, конечная и функциональная). Начальная и конечная имеют нулевую трудоемкость. Функциональные содержат перечень операций соответствующие данному алгоритму. Делятся на 2 вида:
1) вершины реализации процессорных операций,
2) вершины реализации ввода-вывода или операции передачи информации. Для общей оценки должна быть известна трудоемкость каждого оператора.
Введем обозначения:
V – множество операторных вершин, где V0 и Vn – начальная и конечные вершины.
Каждая вершина характеризуется средним числом обращений – ni, где 
. Вершина характеризуется объем работ 
для выполнения операции i-ой вершины. V0=VK=0 Матрица 
характеризует вероятность перехода из i-ой в j-ю. Перед расчетом граф-схемы алгоритма с циклами производят ранжирование. К циклам I – го ранга относятся циклы, не содержащие других циклов. Циклы II- го ранга включают в себя только циклы I-го ранга. Суть заключается в определении трудоемкости тела цикла и с учетом числа повторений находится трудоемкость всего цикла этого ранга. Определенный цикл заменяется эквивалентным оператором.
Пусть даны циклы разных рангов:
С1 С2 С3 …. Сm
Q1 Q2 Q3 … Qm=Q
где Q - суммарная трудоемкость всего алгоритма.
У каждого из этих циклов есть трудоемкость и среднее число повторений циклов i-го ранга.
|
|
|
где ni – среднее число повторений циклов i- го ранга,
tI трудоемкость тела цикла
Формулы:
где Pkl – вероятность перехода по дуге обратного перехода
- трудоемкость тела цикла
Среднее число обращений
где r – множество операторов, из которых происходит обращение в данную вершину Pji.
Вероятность обращения из j-й в i-ую. nj – число обращения к j-той вершине за одну реализацию алгоритма.
Осн.лит. 4[22-46],
Доп. лит.5[6-21]
Контрольные вопросы:
1. Что такое граф-схема алгоритма?
2. В чем определяется трудоемкость алгоритма?
3. В чем суть сетевого метода расчета трудоёмкости алгоритма?
4. Что такое ранг цикла?
5. Как формализовано, определяется число повторений цикла?
|
|
|
