logo
Методические указания по курсовому проектирован

7.7. Оценка времени выполнение программ

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

Рассмотрим экспериментальный метод оценки времени выполнения программы. Реализация метода включает выполнение следующих этапов:

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

.

Обычно функцию времени определяют для худшего случая решения задачи.

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

  2. Составляется система уравнений, где неизвестными величинами являются константы.

  3. Решается система уравнений и определяются значения констант.

Таблица 7.11

№

Название этапа

Результаты выполнения этапа

1

Построение функции времени выполнения программы,

T=c2n2+c1n+c0

2

Проведение экспериментов с программой.

n1=5

t1=0,04

n2=10

t2=0,12 c.

n3=100

t3=10,11 c

3

Составление системы уравнений

52 с2+5c1+c0=0,04

102c2+10c1+c0=0,12

1002c2+100c1+c0=10,11

4

Решение системы уравнений

c2=10-3, c1=10-3, c0=10-2

5

Формируется функция времени

T=10-3n2+10-3n+10-2 (c)

6

Оценивается время выполнения программы на реальных данных.

n=106,

T=10-3(106)2+10-3106+102

109 (c) 1157,4 дня 

 3,2 года

7

Выводы

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

  1. Формируется функция времени, связывающая размер задачи и оценку время выполнения программы.

  2. Оценивается время выполнения программы на реальных данных. В функцию времени подставляются реальная размерность задачи и определяется время выполнения программы.

Рассмотрим пример оценки времени выполнения программы осуществляющая сортировку жителей Казани по возрасту (применяется метод обмена, численность жителей Казани – 1 млн. человек). Результаты выполнения этапов приведены в таблице 7.11.