Оценска сложности алгоритмов

Оценка сложности алгоритмов

Оценка алгоритмов, содержащих ветвления

Для определения максимальной и минимальной сложность необходимо вычислить вес каждой ветви как сумму весов всех входящих в нее вершин и найти максимальное и минимальное значения по всем ветвям соответственно.

Для определения средней сложности необходимо оценить частоты выбора ветвей.

Под частотой ветви понимается отношение числа выполнений программы (алгоритма), при которых исполнились операторы, принадлежащие данной ветви, к общему числу исполнений этой программы.

Средняя сложность программы (ее алгоритма) вычисляется как сумма произведений весов ветвей на их частоты.

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

Пусть управляющий граф программы содержит ветвления, где выбор ветвей определяется условиями C1, C2, C3, …, Cn. Вид управляющего графа представлен на рис. 1.

Рис. 1. Пример управляющего графа с ветвлениями

Проверка условия C1 выполняется всегда, таким образом оно разбивает все ветви на две группы: для первой условие истинно, для второй ­– ложно. Условие C2 разбивает группу ветвей, для которых условие C1 истинно, еще на две группы, для которых истинны условия (C1 and C2) и (C1 and not C2) соответственно. Условие C3 также разбивает группу ветвей, для которых условие C1 ложно, еще на две группы, удовлетворяющих условиям (not C1 and C3) и (not C1 and not C3) соответственно. Для следующих ветвлений (до Cn) этот процесс «разбиения» ветвей на группы можно было бы продолжить.

Выбор ветвей определяется комбинацией входных данных D. Множество комбинаций исходных данных D также можно разбить на две части D1 и D2 (два подмножества), порождаемые условием C1. В свою очередь D1 делится на D3 и D5, а D2 разбивается на D5 и D6 (рис. 2). Каждая область (подмножество D), которая не разбивается больше ни на какие другие более мелкие части, соответствует ветви в управляющем графе (ветви пересекаются в начальной части графа ­– для общих условий, определяющих их выбор). Все такие подмножества комбинаций входных данных (областей на рисунке) обозначим di. В том случае, когда все комбинации исходных данных являются равновероятными, частоту исполнения i‑й ветви можно оценить как отношение мощности подмножества di к мощности всего множества D: pi = | di | / | D |. Если имеются оценки li веса (сложности) i‑й ветви, то сложность такого алгоритма a с ветвлениями можно оценить величиной

,

где k – количество всех ветвей.

Рис. 2. Разбиение множества комбинаций входных данных, соответствующее
примеру управляющего графа с ветвлениями (рис. 1)

Пример. Пусть алгоритм с ветвлением имеет вид

read(X);

if X < 0.5 then Y := (X + 0.5) * 2

else if X < 0.75 then Y := X * 2 + 0.5 + X**2 + X**3

else Y := X

Допустим, что значение переменной X может принадлежать диапазону [0.00, 1.00], причем ввод любого значения из указанного диапазона равновероятен. Тогда вероятность того, что значение X Î [0.00, 0.50), примерно равна вероятности того, что X Î [0.50, 1.00]. В приведенном примере вероятность выбора ветви Y := (X + 0.5) * 2 равна 0.5. При невыполнении условия X < 0.5 выбор ветви определяется проверкой условия X < 0.75. Причем ветви выбираются также равновероятно, поэтому частота выбора каждой равна примерно 0.25. Разбиение всего множества комбинаций (в данном случае каждая комбинация определяется только значением переменной X) показано на рис. 3.

Рис. 3. Геометрическая вероятность ввода значений переменной, определяемая
длинами отрезков числовой прямой (значения равновероятны)

Таким образом, при выполнении программы возможен выбор трех ветвей:

1) ветви Y := (X + 0.5) * 2, соответствующей условию X < 0.5, вес (сложность) которой составляет 5 (ввод, проверка условия, вычисление выражения (2 операции) и присваивание), а вероятность выбора ­– 0.5;

2) ветви Y := X * 2 + 0.5 + X**3, соответствующей условию not(X < 0.5) and (X < 0.75), вес (сложность) которой составляет 10 (ввод, проверка условия X < 0.5, проверка условия X < 0.75, вычисление выражения (6 операций) и присваивание), а вероятность выбора ­составляем 0.25;

3) ветви Y := X, соответствующей условию not(X < 0.5) and not(X < 0.75), вес (сложность) которой составляет 4 (ввод, проверка условия X < 0.5, проверка условия X < 0.75, и присваивание), а вероятность ее выбора ­– примерно 0.25.

Средняя сложность алгоритма составляет

TAvrg = 0,5 ´ 5 + 0,25 ´ 10 + 0,25 ´ 4 = 2,5 + 2,5 + 1 = 6.

Определите максимальную и минимальную сложность приведенного алгоритма.

Оценка алгоритмов, содержащих циклы со счетчиком

Если выражения, определяющие начальное и конечные значения параметра цикла – константы, то можно посчитать, сколько раз будет выполняться цикл, и умножить это число на вес (сложность) тела цикла.

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

Пример 1. Процедура содержит цикл вида

for I := 1 to X do Тело цикла

Допустим, что переменная X может принимать значения от 0 до 100 с равной вероятностью (1/101). Тело цикла выполняется X раз, причем худший случай реализуется при X = 100, а наилучший – при X = 0. Среднее число выполнений тела цикла равно

tAvrg = 1/101´0 + 1/101´1 + 1/101´2 + … + 1/101´100 =
= 1/101´(0+1+2+…+100) = 1/101´(0+100)/2´101 = 50.

Пример 2. Процедура содержит вложенные циклы вида

for I := 1 to X do

for J := I to X do Тело цикла

Допустим, что переменная X может принимать значения от 1 до 5 с равной вероятностью (1/5).

Внешний цикл выполняется X раз. Тело цикла выполняется

X + (X – 1) + (X – 2)  + …  + 1 = X ´ (X + 1)/2

раз, причем худший случай реализуется при X = 5, а наилучший – при X = 1. Таким образом, верхняя граница сложности равна

X ´ (X + 1)/2 = 5 ´ (5 + 1)/2 = 15.

Минимальное число выполнений тела цикла равно

X ´ (X + 1)/2 = 1 ´ (1 + 1)/2 = 1.

Среднее число выполнений тела цикла равно

Пример 3. Оценим сложность алгоритма умножения двух квадратных матриц A и B размерностью N´N и получения в качестве результата третьей матрицы C:

for I := 1 to N do {Цикл 1}

for J := 1 to N do {Цикл 2}

begin

C[I, J] := 0;

for K := 1 to N do {Цикл 3}

C[I, J] := C[I, J] + A[I, K]* A[K, J]

end

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

Сложность алгоритма определяется величиной

Ta (N) = N ´ (T1),

где T1 – сложность тела цикла 1 по I, которая равна

T1 = N ´ (T2),

где T2 – сложность тела цикла 2 по J и

T2 = 1 + N ´ (T3).

Здесь сложность тела цикла 3 по K (T3) равна 3 (умножение, сложение и присваивание), а 1 операция – это присваивание начального значения элементу матрицы C.

Выполняем подстановку и получаем выражение сложности алгоритма через сложность исходных данных:

Ta (N) = N ´ (N ´ (1 + N ´ 3)) = N ´ (N + N 2 ´ 3) = N 2 + N 3 ´ 3 = 3N 3 + N 2.

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

Задание. Сделайте оценку сложности для приведенных примеров с учетом операций, задаваемых в заголовках циклов.

Оценка алгоритмов, содержащих циклы с пред - или постусловием

Оценка этих алгоритмов в общем случае сложнее, т. к. зависимость условия, определяющего, будет ли исполняться тело цикла и число его повторений, от исходных данных может быть достаточно сложной. При этом условие, заданное в цикле, делит все комбинации входных данных на два подмножества: для первого условие выполняется, а для второго – нет. Если комбинация исходных данных такова, что тело цикла выполняется, то необходимо установить зависимость числа повторений от того, как меняются данные. Эти оценки в каждом случае выполняются «индивидуально».

Задания для подготовки к контрольной

Задание 1. Постройте диаграммы Вирта для операторов языка Pascal.

Задание 2. Постройте БНФ (формулы Бэкуса-Наура) для операторов языка Pascal.

Задание 3. Постройте дерево вызовов (используйте написанные на паре описания процедур), дерево разбора и обратную польскую запись для следующих выражений:

ü  (A*B+C/D)*5–A*(2*B/(C+D))

ü  A+B–C+D

ü  (((1+D)))

ü  A+(C*(A–5+D)*B)–D

Задание 4. В программе на языке Pascal выделите лексемы (возьмите фрагменты любых программ), выпишите синтаксические правила, которым удовлетворяют использованные в программе конструкции.

Задание 5. В программе на языке Pascal выделите лексемы (возьмите фрагменты любых программ).

Задание 6. Дайте понятие грамматики и определите по виду приведенных правил, к какому классу относится язык L(G) (используйте классификацию по Хомскому):

G = (A, N, R, S)

A = {a, b, c, d, f}

N = {A, B, C, D, F}

R: F ::= AaBb

A ::= c [ C | D ] d

B ::= { dD } f

aCb ::= aDb

cCd ::= cAd

D ::= aA | bB

S = F

Является ли строка

cacddadacbdfdb

словом в языке L(G)? Покажите порядок разбора (вывода) строки.

Задание 7. Оцените сложность процедуры (в зависимости от исходных данных V):

1.

procedure F (V: integer);

var I, J,K: integer;

S, T: real;

begin

T := 0;

for I:=1 to V do

begin

S:=I*123;

for J:=V downto 2 do

for K:=1 to I+V*V do T:=(T+S)/5

end

end;

2.

procedure P (V: integer; var B: real);

var M, K: integer;

A: real;

begin

for M:=1 to V do

begin

A:=M+2;

K:=2;

while K<V do

begin

A:=A–V+M*K;

B:=2–A;

K:=K*K

end

end

end;