ГоловнаЗворотній зв'язок
Главная->Математика і інформатика->Содержание->1.5. Вычисление времени выполнения программ

Алгоритмы структуры данных

1.5. Вычисление времени выполнения программ

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

Пусть Т1(n) и T2(n) — время выполнения двух программных фрагментов Р1 и Р2, Т1(n) имеет степень роста О(f(n)), а Т2(n) — O(g(n)). Тогда Т1(n) + T2(n), т.е. время последовательного выполнения фрагментов Р1 и Р2, имеет степень роста О(mах(f(n), g(n))). Для доказательства этого вспомним, что существуют константы c1, с2, n1 и n2 такие, что при n ≥ n1 выполняется неравенство T1(n) ≤ c1f(n), и, аналогично, Т2(n) ≤ с2g(n), если n ≥ n2. Пусть no = mах(n1, n2). Если n > no, то, очевидно, что Т1(n) + Т2(n) ≤ c1f(n) + c2g(n). Отсюда вытекает, что при n ≥ nо справедливо неравенство Т1(n) + T2(n) ≤ (c1 + с2)mах(f(n), g(n)). Последнее неравенство и означает, что Т1(n) + T2(n) имеет порядок роста О(mах(f(n), g(n))).

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

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

 

                f(n)=     n4, если n четное;                                     

   n2, если n нечетное,                                         

              

                  g(n)=   n2, если n четное;

    n3 , если n нечетное.

 

В данном случае правило сумм можно применить непосредственно и получить время выполнения О(mах(f(n), g(n)), т.е. n4 при n четном и n3, если n нечетно.

Из правила сумм также следует, что если g(n) ≤ f(n) для всех n, превышающих n0, то выражение О(f(n) + g(n)) эквивалентно O(f(n)). Например, О(n2 + n) то же самое, что О(n2).

Правило произведений заключается в следующем. Если Т1(n) и Т2(n) имеют степени роста О(f(n)) и O(g(n)) соответственно, то произведение Т1(n)T2(n) имеет степень роста O(f(n)g(n)). Вы можете самостоятельно доказать это утверждение, используя тот же подход, который применялся при доказательстве правила сумм. Из правила произведений следует, что О(сf(n)) эквивалентно О(f(n)), если с — положительная константа. Например, О(n2/2) эквивалентно О(n2).

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

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

Листинг 1. 4.

procedure bubble { var A: array [l..n] of integer );

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

var

і, j, temp: integer;

begin

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

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

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

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

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

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

(6)                                 A[j] :=  temp;

 end

end;   { bubble }

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

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

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

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

,

которое имеет порядок О(n2). Таким образом, программа "пузырька" выполняется за время, пропорциональное квадрату числа элементов, подлежащих упорядочиванию. В тeмe 8 мы рассмотрим программы с временем выполнения порядка О(п logn), которое существенна меньше О(п ), поскольку при больших n logn (eсли не указано другое, то будем считать, что все логарифмы определены по основанию 2. Однако отметим, что выражение O(logn) не зависит от основания логарифма, поскольку logan= clogbn, где с =:logab.) значительно меньше n.

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

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

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

2.    Время выполнения последовательности операторов определяется с помощью правила сумм. Поэтому степень роста времени выполнения последовательности операторов без определения констант пропорциональности совпадает с наибольшим временем выполнения оператора в данной последовательности.

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

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

 

 

12