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

На практике для определения времени выполнения программы пользуются несколькими базовыми принципами:

1. Время выполнения операторов присваивания, чтения и записи обычно имеет порядок О(1). Исключение составляют операторы присваивания с вызовом функции в правой части. Y=fact(x).

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

Пусть T₁(n) и T₂(n) – время выполнения двух программных фрагментов Р₁ и Р₂, T₁(n) имеет степень роста O(f(n)), а T₂(n) – O(g(n)). Тогда T₁(n)+ T₂(n), т.е. время последовательного выполнения фрагментов Р₁ и Р₂ , имеет степень роста O(max(f(n),g(n))).

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

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

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

6. Для подсчета времени T(n) выполнения рекурсивной процедуры выводится рекуррентное соотношение (уравнение или неравенство) для T(n), где в правой части соотношения присутствуют значения T(k), k=1,…,n .

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

Программа вычисления факториала.

(1) (2) (3)

long int fact(int n) { if (n<=1) return 1; else return ( n * fact(n-1) ); }

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

Обозначим через T(n) время выполнения программы с объемом входных данных n. Время выполнения строк (1) и (2) имеет порядок О(1), а для строки (3) – О(1)+Т(n-1). Таким образом для некоторых констант с1 и с2 имеем

Полагая, что n>2 получим T(n)=c1+T(n-1)=c1+(c1+T(n-2))=2c1+T(n-2).

Полагая, что n>3 получим T(n)=c1+T(n-1)=c1+(c1+T(n-2))=2c1+T(n-2) =

2c1+(c1+T(n-3))=3c1+T(n-3).

По индукции для n>i получим T(n)=i*c1+T(n-i), полагая i=n-1 получим

T(n)=(n-1)*c1+T(1)=(n-1)*c1+c2.

Отсюда следует, что T(n) имеет степень роста О(n).

Общий метод решения рекуррентных соотношений состоит в последовательном раскрытии T(k) в правой части до тех пор, пока не получится формула, у которой в правой части отсутствует Т. При этом часто приходится находить суммы последовательностей. Если значения таких сумм нельзя вычислить точно, то для сумм находятся верхние границы, что позволяет получить верхние границы для T(n).

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

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

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