Proc(a,y);

b: =4*d – 10 mod b;

Известно, что сложность процедуры Proc равна 2V+1.

Построим управляющий граф, снизу от каждой вершины графа напишем ее вес.

T_a(V)=2V+7.

2. Управляющий граф содержит разветвления, но не содержит циклов. Расчёт сложности зависит от того, рассматриваем мы худший, лучший или средний случай.

Поскольку для вычисления средней оценки сложности используется вероятностный подход, приведем начальные понятия из теории вероятности:

· Вероятность события (p) есть объективная мера возможности события, выражаемая числом, удовлетворяющим условию 0 ≤ p ≤ 1.

· Достоверное событие, т.е. то событие, которое непременно произойдет, имеет вероятность равную 1.

· Невозможное событие имеет вероятность равную 0.

Пример:

Рассмотрим фрагмент алгоритма:

If a< b then x: =a else x: =b-2;

Известно, что вероятность выполнения условия a< b равна .

Построим управляющий граф, внутри каждой вершины графа напишем ее вес.

Вычислим веса ветвей T₁ = 1+1+0 = 2, T₂ = 1+2+0 = 3. T_min = 2, T_max = 3. Для определения средней оценки сложности вычислим вероятности выполнения ветвей.

p₁ = по условию,

p₂ = 1 – p₁ = , т.к. события «выполнилась 1 ветвь» и «выполнилась 2 ветвь» несовместны и образуют полную группу.

T_average = p₁T₁+p₂T₂ = ·2+ ·3 = 2 = 2, 25.

10) Оценка сложности циклических алгоритмов. Примеры.

Управляющий граф содержит цикл, но не содержит вложенных циклов. В этом случае, временная сложность зависит от количества повторений цикла.

Введем обозначения:

T_{тела цикла} – временная сложность операторов, выполняемых в теле цикла;

T_{условия} – количество операций, выполняемых при проверке условия цикла;

k – количество повторений тела цикла;

T(k) – временная сложность выполнения цикла, как функция, зависящая от параметра k.

Рассмотрим часто встречающиеся случаи:

1) Цикл с параметром c заголовком for i: =1 to n do

k = n, T(k) = k∙ T_{тела цикла}.

2) Цикл с параметром с заголовком в общем виде for i: =a to b do

k = (b–a)+1, T(k) = k∙ T_{тела цикла}.

3) Цикл с предусловием While … Do. Условие в таком цикле всегда проверяется на 1 раз больше по сравнению с количеством выполнений тела цикла.

T(k) = (k+1) ∙ T_{условия} + k∙ T_{тела цикла}, k ≥ 0.

4) Цикл с постусловием Repeat … Until. Количество выполнений тела цикла совпадает с количеством проверок условия цикла, минимально тела цикла выполняется 1 раз.

T(k) = k ∙ T_{условия} + k∙ T_{тела цикла}, k ≥ 1.

В случае, когда число повторений цикла равно константе, нижняя, верхняя и средняя оценки сложности совпадают, и их вычисление не требует особых пояснений. Рассмотрим случай, когда число повторений цикла является переменной величиной. В этом случае:

– Нижняя оценка сложности T_min соответствует случаю, когда тело цикла выполняется минимально возможное число раз, обозначим это число k_min.

– Верхняя оценка сложности T_max соответствует случаю, когда тело цикла выполняется максимально возможное число раз, обозначим это число k_max.

– Средняя оценка сложности вычисляется как сумма произведений вероятности того, что цикл выполнится k раз, на сложность алгоритма при k итерациях цикла, при этом значение k последовательно пробегает все значения от k_min до k_max.

T_average =

Пример:

Рассмотрим фрагмент алгоритма, в котором n – целое число, n и все значения n равновероятны.

x: =0;

For i: =1 to n do

x: =x+i;

Построим управляющий граф, внутри каждой вершины графа напишем ее вес.

Функция сложности T(k) = 1+2k. Поскольку количество повторений тела цикла k=n, можно переписать функцию сложности по-другому T(n) = 1+2n. Таким образом, параметром V, характеризующим сложность входных данных, является n (V=n).

Минимально цикл выполняется 0 раз, следовательно, T_min = T(0) = 1.

Максимально возможное число повторений тела цикла равно 10, значит T_max=T(10)=1+2∙ 10=21.

Поскольку все значения n равновероятны p₀ = p₁ = … = p₁₀ = .

T_avareage = ∙ T(0) + ∙ T(1) + … + ∙ T(10) = ∙ (1 + 3 + 5 + …+ 21) = ∙ = 11.

Управляющий граф содержит вложенные циклы. Возможно два случая: