6.2.Время выполнения программ

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

Время выполнения программы обычно определяют как функцию от длины исходных данных. Обычно говорят, что время выполнения программы выражается функцией T(n) от входных данных размера n.

Для многих программ время выполнения является функцией входных данных, а не их размера. В этом случае T(n) определяется как функция времени выполнения программы в наихудшем случае, т.е. как максимум времени выполнения по всем входным данным размера n. Также иногда рассматривают T_ср(n) как среднее время выполнения по всем входным данным размера n. На практике среднее время найти сложнее, чем наихудшее.

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

Для описания скорости роста функций времени выполнения программ используется O-символика. Например, когда говорят, что время выполнения T(n) некоторой программы имеет порядок O(n²) (читается «о-большое от n в квадрате» или «о от n в квадрате»), то подразумевают, что существуют положительные константы c и n₀ такие, что для всех nn₀ выполняется неравенство T(n) T(n), где T(n)=cn².

Пример. Пусть T₁(n)=(n+5)². Тогда T₁(n) будет иметь порядок O(n²). Действительно, если положить n₀=1 и c=37, то легко показать, что для n1 будет выполняться неравенство (n+5)²T₂(n), T₂(n)=36n².

В общем случае будем говорить, что T(n) имеет порядок O(f(n)), если существуют положительные константы c и n₀ такие, что для всех nn₀ выполняется неравенство T(n)cf(n).

Пример. Пусть T₃(n)=3n³+2n². Данная функция имеет порядок O(n³). Действительно, если положить n0=0 и c=5, то легко показать, что для n0 будет выполняться неравенство 3n³+2n²5n³. Можно сказать, что T₃(n)=3n³+2n² имеет порядок O(n⁴), но это более слабое утверждение, чем то, что T₃(n)=3n³+2n² имеет порядок O(n³).

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

Пример. Пусть одна и та же задача может быть решена с помощью двух программ P₁, P₂ или P₃, имеющих функции времени T₁(n)=(n+5)², T₂(n)=36n², T₃(n)=3n³+2n² соответственно. Значения данных функций для различных значений n сведены в табл.6.1. Из таблицы видно, что функция T₃(n) для n=1 и n=2 имеет меньшее значение, чем функция T₁(n). Поэтому несмотря на то, что функция T₃(n) имеет порядок O(n³), а функция T₁(n) - O(n²), использование программы P₃ при n=1 и n=2 более предпочтительно, чем использование программы P₁. Также функция T₃(n) для n=1,2,…,11 имеет меньшее значение, чем функция T₂(n). Поэтому для n=1,2,…,11 предпочтительнее использовать программу P_З чем программу P₂, несмотря на то, что порядок функции T₃(n) - O(n³), а функция T₂(n) - O(n²).

Таблица 6.1

Значения функций времени выполнения программ

n	T1(n)= (n+5)^2	T2(n)= 36n^2	T3(n)= 3n^3+2n^2	n	T1(n)= (n+5)^2	T2(n)= 36n^2	T3(n)= 3n^3+2n^2
1	36	36	5	7	144	1764	1127
2	49	144	32	8	169	2304	1664
3	64	324	99	9	196	2916	2349
4	81	576	224	10	225	3600	3200
5	100	900	425	11	256	4356	4235
6	121	1296	720	12	289	5184	5472