Оценка времени выполнения алгоритмов
ЛАБОРАТОРНАЯ
РАБОТА 3
Тема:
Оценка времени выполнения алгоритмов
1. Цель работы
Приобретение и закрепление навыков оценивания
времени выполнения алгоритмов.
. Прорабатываемые темы
Построение и анализ алгоритмов.
. Постановка задачи
Оценить время выполнения алгоритма,
реализованного в ЛР №1. Сравнить с результатами замеров при разных значениях
ХМ. Построить график зависимости T=F(XM).
Выполнение работы
Для исследования времени выполнения алгоритма на
основе программы(ЛР№1) ,возьмем 4 значения Xm(4,5,6,9).
Текст программы:LAB1;
arrp: array[1..5050] of integer; { Сжатая
таблица
}
XM : integer; { Максимальные индексы в таблице }
start,finish,x1,x2:longint;,hour,min,sec,ssec:word;
{==== Функция перевычисления индексов ====}
{ y,x - индексы в 2-мерном массиве. Ф-ция
возвращает индекс в 1-мерном массиве }NewIndex(y, x : integer) : integer;
var i, d,k: integer;:=0;:=0;i:=1 to
y-1 do d:=d+XM-i+1;:=d+x-y+1;;
{====
Функция записи в сжатое представление массива ====}
{
y, x - индексы в 2-мерном массиве, value - записываемое значение.
Функция
возвращает записываемое значение или 0 - если (x,y)
beginx < y then
PutTab:=0begin[NewIndex(y,x)]:=value;
PutTab:=value;;;
{====
Функция выборки из сжатого представления массива ====}
{
y, x - индексы в 2-мерном массиве. Функция возвращает выбранное значение
}GetTab(y,x: integer) : integer;
beginx < y then
GetTab:=0GetTab:=arrp[NewIndex(y,x)];;GetTime:longint;:=sec*100+min*6000+ssec;
end;
{=============
Главная программа ===================}, y : integer; { Индексы в 2-мерном
массиве }, h: integer;
{=====
Проверка формирования массива ======}:=10;
{
Запись элементов в 1-мерный массив }
k:=3; время
массив программаy:=1 to XM dox:=3 to XM do begin:=PutTab(y,x,k);
k:=k+3;;
{ Распечатка матрицы
}('===== Matriza =====');:=time;y:=1 to XM do beginx:=1 to XM do
write(GetTab(y,x):3);;;:=time;:=finish-start;
{ Распечатка внутреннего представления матрицы
}('===== Matriza (vnutr.predstavlenie) =====');:=time;y:=1 to 55 do
write(arrp[y]:4);:=time;:=finish-start;;('Time1= ',x1);('Time2= ',x2);;
writeln;readln;
end.
Результаты
работы программы:=4
Рисунок1-Результат
работы программы при Xm=4
=5
Рисунок2-результат
работы программы при Xm=5
Xm=6
Рисунок3-результат
работы программы при Xm=6
=9
Рисунок4-результат
работы программы при Xm=9
График
зависимости T=F(XM):
Значение
времени для графика будет взято из Time1(по начальному значению времени
выполнения алгоритма):
Рисунок5-график
зависимости T=F(Xm)
Проведем
оценку времени выполнения:=c*n;где с-константа;n-к-во задействованного времени;
Т=4*n*n*n*n=15812мс.
Вывод:
в ходе выполнения ЛР, я приобрел навыки в оценивания времени выполнения
алгоритмов.