§4. Свойства асимптотических оценок функций.

Теорема 1.

1. Если и , то , т. Е.

2. Если , то , т. е.

3. 

4. Если , то , т. е.

5. – правило произведений.

6. –правило сумм, где под функцией понимается функция такая, что =

Доказательство

1. Т. к. , то .

Т. к. , то по определению 1 §3 .

2. Пусть причем по определению 1 §3 . Пусть , причем .

Обозначим . Тогда .

Таким образом , т. е. и, таким образом, .

3. Пусть , . Тогда , причем по определению 1 §3

5. Пусть , ,

6. Пусть ,

Тогда , . Теорема доказана.

Замечание 1. Правило сумм (Теорема 1 (6)) используется для вычисления времени выполнения последовательных фрагментов программ.

Пусть два программных фрагмента и выполняются соответственно за время и . Время их последовательного выполнения

Лемма 1. Если существует конечный предел =k, то при .

Используя определение 1 §3 или лемму 1 можно доказать следующую теорему.

Теорема 2.

1. .

2. 

3. Пусть . Тогда

4. .

§5. Практический анализ эффективности программ.

Приведем общие правила анализа программ без определения констант пропорциональности:

1. Время выполнения операторов присваивания обычно имеет порядок .

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

2. Временная сложность программных фрагментов, выполняемых последовательно, оценивается а) при фиксированном количестве фрагментов с помощью правила сумм (см.Т.1§4): б) при количестве программных фрагментов, зависящем от n (в т.ч. в цикле, где число итераций зависит от n), применяется свойство: (1)

3. Время выполнения условных операторов if-then-else состоит из

а) времени вычисления логического выражения, стоящего после if (обычно это время ).

б) наибольшего из времен выполнения операторов групп then и else.

4. Время выполнения цикла – сумма времени выполнения всех итераций цикла, включая проверку условия прекращения (обычно ).

5. Для программ, содержащих несколько процедур, среди которых нет рекурсивных:

а) определить время выполнения процедуры , не имеющей вызовов других процедур (такая существует, например, это самая внутренняя из вложенных процедур);

б) определить время выполнения процедур, вызывающих эту процедуру и т. д.

в) определить время выполнения всех процедур найти время выполнения всей программы.

Пример 1. Проанализируем программу сортировки методом «пузырька». Массив А упорядочивается по возрастанию.

procedure bubble(var A: array[1..n] of integer)

var

i, j, temp : integer;

begin

(1) for i := 1 to n-1 do

(2) for j := n downto i + 1 do

(3) if A[j -1] > A[j] then

begin

{Переставляем местами A[j -1] и A[j ]}

(4) temp := A[j-1];

(5) A[j-1] := A[j];

(6) A[j] := Temp ;

end;

end

Пусть n – объем вводимых данных, т. е. количество элементов, подлежащих сортировке.

Проанализируем время выполнения программы, переходя от внутренних операторов к внешним.

Группа операторов присваивания (4)-(6) выполняется за время каждый (см. п.1). Вся последовательность (4)-(6) по правилу п.2 за время .

Для оператора if в строке (3) вычисление логического условия A[j -1] > A[j] требует времени (см. п. 3).

Наибольшее время выполнения имеет группа операторов then (4)-(6) - как показано выше, . Таким образом, время выполнения группы (3) – (6) требует времени .

Цикл (2)-(6) выполняется n-i раз, причем на каждом проходе группа операторов тела цикла (3)-(6) требует времени

Итого, применяя свойство (1), получим .

Цикл (1)-(6) выполняется n-1 раз при i от 1 до n-1, каждый раз тело цикла требует времени , таким образом, весь цикл, согласно свойству (1), выполнится за время

Полученная сумма является арифметической прогрессией, члены которой , , тогда сумма первых членов будет равна , то есть искомое время

Согласно правилам пп. 1-5 найдена эффективность, то есть асимптотическая временная сложность алгоритма в худшем случае.