Geum.ru

Программа дисциплины «Информатика и программирование»

Вид материалаПрограмма дисциплины

Содержание


Оценка алгоритмов, содержащих циклы со счетчиком
X раз, причем худший случай реализуется при X = 100
X = 5, а наилучший – при X = 1
Оценка алгоритмов, содержащих циклы с пред- или постусловием
Подобный материал:
1   2   3   4   5   6   7

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


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

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

Пример 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 размерностью NN и получения в качестве результата третьей матрицы 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.

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

T (N) = N  (T1),

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

T1 = N  (T2),

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

T2 = 1 + N  (T3).

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

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

T (N) = N  (N  (1 + N  3)) = N  (N + N 2  3) = N 2 + N 3  3 = 3N 3 + N 2.


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

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

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


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