Вычисление времени работы алгоритма.

⇐ ПредыдущаяСтр 15 из 45Следующая ⇒

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

Поясним сказанное на примерах. Пусть нужно выполнять некоторую обработку последовательности из n чисел, где n может меняться (скажем, нужно найти минимальное из этих чисел). Пусть у нас есть две программы для решения задачи, времена работы которых приблизительно равны C₁n и C₂n², где C₁ и C₂ – константы, не зависящие от n. Ясно, что при больших n первая программа будет работать быстрее. Скорее всего, при малых n она будет работать медленнее (именно так обычно бывает в практических случаях), а это означает, что C₁ > C₂. Пусть C₁ в 5 раз больше C₂. Сравнив выражения для времен работы C₁n=5C₂n и C₂n², можно увидеть, что при n> 5 время работы первой программы меньше, а при n< 5 быстрее вторая программа. Разумеется, ввиду приближенности оценок времени граничное значение n=5 тоже устанавливается приближенно.

Из наших гипотетических рассмотрений следуют два вывода. Первый: даже приближенные оценки «с точностью до константы» могут оказаться полезными при сравнении алгоритмов. Второй: обычно нельзя сказать, что какой-то один алгоритм решения задачи всегда самый быстрый. Некоторый алгоритм может превосходить другой для какого-то одного набора исходных данных и уступать ему для другого набора.

Остановимся на вопросе о выборе такой характеристики исходных данных, которая определяла бы время работы программы. Эта характеристика называется размером задачи. Для разных задач на время решения влияют разные свойства исходных данных. Так, для задач типа поиска минимума или упорядочивания заданных чисел, где каждое число рассматривается как единое целое, размером задачи является количество исходных чисел. Для задачи разложения на простые сомножители размером естественно считать величину числа. Выбор размера задачи основан на некотором, хотя бы общем представлении об алгоритме решения. Обратимся к задаче вычисления 2ⁿ. Учитывая, что возведение в степень будет выполняться путем последовательного умножения, выберем в качестве размера показатель степени N. Другим возможным кандидатом на роль размера является число цифр в результате. В нашей задаче число цифр в числе 2ⁿ практически пропорционально N, поэтому оба размера эквиваленты.

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

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

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

Для цикла For I: =A to B

Число повторений равно B-A+1, если B³ A-1 (1)

Для цикла For I: =A downto B

В формуле следует поменять местами A и В.

Эта формула справедлива, если программа приступает к выполнению цикла всего один раз. Рассмотрим, как быть, если этот цикл вложен в другой и его выполнение повторяется много раз. Договоримся о терминологии. Когда нам понадобиться выяснить число повторений инструкций внутри цикла, будем называть это число числом выполнений тела цикла. Число выполнений заголовка цикла – это сколько раз начинает выполняться весь цикл. Рассмотренная формула дает не что иное, как число выполнений тела цикла при однократном выполнении его заголовка. Если рассматриваемый цикл вложен в другой, то его заголовок будет выполняться многократно, и, чтобы найти общее число выполнений тела, следует просуммировать числа, даваемые рассмотренной формулой, при всех выполнениях заголовка цикла. В качестве простого примера применения этой формулы проанализируем следующий фрагмент программы:

For J: =1 To N Do Begin (*Цикл 1*)

For K: =1 To M Do Тело цикла 2;

For J: =1 Downto N Do Тело цикла 3;

End;

Тела циклов 2 и 3 не содержат циклов, M и N – некоторые достаточно большие константы. Оценим число повторений циклов 2 и 3. оба они вложены в цикл 1, число повторений которого легко находится по формуле; оно равно N-1+1=N. При каждом из этих повторений тело цикла 2 выполняется M-1+1=M раз. Поскольку M – константа, общее число повторений цикла 2 равно N₂=N*M. Тело цикла 3 выполняется N-J+1 раз при каждом выполнении тела цикла 1. это число в отличие от M меняется при выполнении цикла 1; поэтому нельзя просто перемножить два числа: необходимо суммировать все числа выполнений тела цикла 3. заметим, что при выполнении цикла 1 переменная J принимает все значения от 1 до N (именно это записано в заголовке цикла 1). Таким образом, общее число выполнений тела цикла 3 равно N₃= . Эта сумма арифметической прогрессии; она равна (N+1)*N/2. так как время вычисляется приближенно, то, пренебрегая 1 по сравнению с N, несколько упростим формулу: N₃ приближенно равно N²/2. Сравнивая N₂ и N₃, нельзя заключить, что одно их этих чисел значительно превосходит другое. Напротив, при некоторых M и N они будут одного порядка. Например, если M=N, то N₂ примерно в два раза больше N₃. поэтому в формулу для времени работы придется включить два слагаемых, отвечающих обоим циклам. Считая времена однократного выполнения тел циклов примерно постоянными и обозначив их T₂ и T₃, получим следующую приближенную формулу для общего времени работы: T=M*V+(N²/2)*T₃.

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

Более детальную информацию о времени работы можно получить по результатам измерения фактического времени работы программы для различных исходных данных. С помощью этих экспериментальных данных можно оценить неизвестные постоянные, входящие в формулу (в нашем случае T₂ и T₃).

⇐ Предыдущая 10 11 12 13 141516 17 18 19 Следующая ⇒