Главная Промышленная автоматика.

Пусть Ti(n)n Ti(n) - время выполнения двух программных фрагментов Pi и р2, Ti(n) имеет степень роста 0(/(п)), а ТгСп) - 0(g(n)). Тогда Ti(n) + Tjlra), т.е. время последовательного выполнения фрагментов Pi и Р, имеет степень роста 0(тах(/(п), g(n))). Для доказательства этого вспомним, что существуют константы Ci, С2, Til и "2 такие, что при п > rii выполняется неравенство Ti(n)< cif(n),u, аналогично, Т2{п)< C2g{n), если п > «2- Пусть По = тах(п1, п). Если « > По, то, очевидно, что Ti(n)+ T2in)< Cif(n)+ C2g(n). Отсюда вытекает, что при п > по справедливо неравенство Ti(n)+ Т2(п)< (ci + С2)гаа.-х.(Кп), g(n)). Последнее неравенство и означает, что Ti(n)+ Т2(п) имеет порядок роста 0(тах(/(п), g{n))).

Пример 1.8. Правило сумм, данное выще, используется для вычисления времени последовательного выполнения программных фрагментов с циклами и ветвлениями. Пусть есть три фрагмента с временами выполнения соответственно 0(п),. О(п) и 0(п logn). Тогда время последовательного выполнения первых двух фрагментов имеет порядок 0(тах(л, п)), т.е. О(п). Время выполнения всех трех фрагментов имеет порядок 0(max(n, п logn)),это то же самое, что О(п). П

В общем случае время выполнения конечной последовательности программных фрагментов, без учета констант, имеет порядок фрагмента с наибольщим временем выполнения. Иногда возможна ситуация, когда порядки роста времен нескольких фрагментов несоизмеримы (ни один из них не больще, чем другой, но они и не равны). Для примера рассмотрим два фрагмента с временем выполнения 0(f{n)) и 0(5(п)),где

, , п,если л четное; п , если л нечетное, [л , если л нечетное.

В данном случае правило сумм можно применить непосредственно и получить время выполнения 0(тах(Дл), gin)), т.е. при п четном и п, если п нечетно.

Из правила сумм также следует, что если g(n) <f(n) для всех л, превыщающих По, то выражение 0(f{n) + g(n)) эквивалентно 0(Дп)). Например, 0(п + л) то же самое, что О(п).

Правило произведений заключается в следующем. Если Ti(n) и Т2(п) имеют степени роста 0(f{n)) и 0((п))соответственно, то произведение Г1(п)Г2(п)имеет степень роста 0(f(n)g(n)). Читатель может самостоятельно доказать это утверждение, используя тот же подход, который применялся при доказательстве правила сумм. Из правила произведений следует, что 0{cf{n)) эквивалентно 0(/(п)),если с - положительная константа. Например, 0{п/2} эквивалентно 0(л).

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

Пример 1.9. Рассмотрим программу сортировки bubble (пузырек), которая упорядочивает массив целых чисел в возрастающем порядке методом "пузырька" (листинг 1.4). За каждый проход внутреннего цикла (операторы (3)-(6)) "пузырек" с наи-меньщим элементом "всплывает" в начало массива.

Листинг 1.4. Сортировка методом „пузырька"

procedure bubble ( var А: array [1. .л] of integer ) ;

{ Процедура упорядочивает массив А в возрастающем порядке }

i, j, temp: integer; begin

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

(2) for J := n down to i + 1 do

(3) if Alj - 1] > Alj] then begin

{ перестановка местами A[j-1] и A[j] }

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



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

(6) A[j] := temp; end

end; { bubble }

Число элементов n, подлежащих сортировке, может служить мерой объема входных данных. Сначала отметим, что все операторы присваивания имеют некоторое постоянное время выполнения, независящее от размера входных данных. Таким образом, операторы (4) - (6) имеют время выполнения порядка 0(1). Запись 0(1) означает "равнозначно некой константе". В соответствии с правилом сумм время выполнения этой группы операторов равно 0(тах(1, 1, 1)) = 0(1).

Теперь мы должны подсчитать время выполнения условных и циклических операторов. Операторы if и for вложены друг в друга, поэтому мы пойдем от внутренних операторов к внешним, последовательно определяя время выполнения условного оператора и каждой итерации цикла. Для оператора if проверка логического выражения занимает время порядка 0(1). Мы не знаем, будут ли выполняться операторы в теле условного оператора (строки (4) - (6)), но поскольку мы ищем наихудшее время выполнения, то, естественно, предполагаем, что они выполняются. Таким образом, получаем, что время выполнения группы операторов (3) - (6) имеет порядок 0(1).

Далее рассмотрим группу (2) - (6) операторов внутреннего цикла. Общее правило вычисления времени выполнения цикла заключается в суммировании времени выполнения каждой итерации цикла. Для операторов (2) - (6) время выполнения на каждой итерации имеет порядок 0(1). Цикл выполняется и - i раз, поэтому по правилу произведений общее время выполнения цикла имеет порядок 0((п - i) х 1), что равно 0(п - г).

Теперь перейдем к внешнему циклу, который содержит все исполняемые операторы программы. Оператор (1) выполняется и - 1 раз, поэтому суммарное время выполнения программы ограничено сверху выражением

5(л ~0 = п(« = п/2- л/2,

которое имеет порядок О(п). Таким образом, программа "пузырька" выполняется за время, пропорциональное квадрату числа элементов, подлежащих упорядочиванию. В главе 8 мы рассмотрим программы с временем выполнения порядка 0(n\ogn), которое существенно меньше О(п), поскольку при больщих и logn значительно меньше и. П

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

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

1. Время выполнения операторов присваивания, чтения и записи обычно имеет порядок 0(1). Есть несколько исключений из этого правила, например в языке PL/1, где можно присваивать большие массивы, или в любых других языках, допускающих вызовы функций в операторах присваивания.

2. Время выполнения последовательности операторов определяется с помощью правила сумм. Поэтому степень роста времени выполнения последовательности опе-

Если не указано другое, то будем считать, что все логарифмы определены по основанию 2. Однако отметим, что выражение O(logn) не зависит от основания логарифма, поскольку logon = elogbn, где с = log„b.



раторов без определения констант пропорциональности совпадает с наибольшим временем выполнения оператора в данной последовательности.

3. Время выполнения условных операторов состоит из времени выполнения условно исполняемых операторов и времени вычисления самого логического выражения. Время вычисления логического выражения обычно имеет порядок 0(1). Время для всей конструкции if-then-else состоит из времени вычисления логического выражения и наибольшего из времени, необходимого для выполнения операторов, исполняемых при значении логического выражения true (истина) и при значении false (ложь).

4. Время выполнения цикла является суммой времени всех исполняемых итераций цикла, в свою очередь состоящих из времени выполнения операторов тела цикла и времени вычисления условия прекращения цикла (обычно последнее имеет порядок 0(1}}. Часто время выполнения цикла вычисляется, пренебрегая определением констант пропорциональности, как произведение количества выполненных итераций цикла на наибольшее возможное время выполнения операторов тела цикла. Время выполнения каждого цикла, если в программе их несколько, должно определяться отдельно.

Вызовы процедур

Для программ, содержащих несколько процедур (среди которых нет рекурсивных), можно подсчитать общее время выполнения программы путем последовательного нахождения времени выполнения процедур, начиная с той, которая не имеет вызовов других процедур. (Вызов процедур мы определяем по наличию оператора call.) Так как мы предположили, что все процедуры нерекурсивные, то должна существовать хотя бы одна процедура, не имеющая вызовов других процедур. Затем можно определить время выполнения процедур, вызывающих эту процедуру, используя уже вычисленное время выполнения вызываемой процедуры. Продолжая этот процесс, найдем время выполнения всех процедур и, наконец, время выполнения всей программы.

Если есть рекурсивные процедуры, то нельзя упорядочить все процедуры таким образом, чтобы каждая процедура вызывала только процедуры, время выполнения которых подсчитано на предыдущем шаге. В этом случае мы должны с каждой рекурсивной процедурой связать временную функцию Т(л), где п определяет объем аргументов процедуры. Затем мы должны получить рекуррентное соотношение для Т(п), т.е. уравнение (или неравенство) для Т(п), где участвуют значения T(fe) для различных значений к.

Техника решения рекуррентных соотношений зависит от вида этих соотношений, некоторые приемы их решения будут показаны в главе 9. Сейчас же мы проанализируем простую рекурсивную программу.

Пример 1.10. В листинге 1.5 представлена программа вычисления факториала пХ, т.е. вычисления произведения целых чисел от 1 до п включительно.

Листинг 1.5. Рекурсивная программа вычисления факториала

function fact ( п: integer ) : integer; { factin) вычисляет п! } begin

(1) if n <= 1 then

(2) fact:= 1 else

(3) fact: n * fact(n - 1) end; { fact }

Естественной мерой объема входных данных для функции fact является значение п. Обозначим через Т(п) время выполнения программы. Время выполнения для строк





0 1 2 3 4 5 6 [7] 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0039