Лабораторная работа № 2 «Оценка вычислительной сложности алгоритмов».

Цель работы: знакомство с элементами теории сложности и освоение методов оценки вычислительной сложности алгоритмов

Теоретические сведения

Сложность алгоритма определяется вычислительными мощностями, необходимыми для его исполнения. Вычислительную сложность алгоритма обычно определяют двумя параметрами Т (временная сложность) и S (пространственная сложность или требования к памяти ). Параметры Т и S выражают как функции от n, где n – размер входных данных, подлежащих обработке.

Вычислительную сложность алгоритма выражают через символ «О большое», указывающий порядок вычислительной сложности. Оценка вычислительной сложности наглядно показывает, как объём входных данных влияет на требования в времени выполнения и объёму памяти. Алгоритмы классифицируют в соответствии с их временной и пространственной сложностью (таблица 2).

Таблица 2 Классификация алгоритмов по сложности

№ п/п	Класс	Сложность	Число операций при n=10^6
	Постоянные	O (1)	1
	Линейные	O (n)	10^6
	Квадратичные	O (n^2)	10^12
	Кубические	O (n^3)	10^18
	Логарифмические	O (nLog(n))	10^8
	Экспоненциальные	O (2^n)	10^301030

На рисунке 1 построены графики, соответствующие классам алгоритмов № 2-4.

Рисунок 1 Функции времени выполнения алгоритмов № 2–6

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

1. Правило сумм. Пусть Т₁(n) и Т₂(n) – время выполнения двух программных фрагментов P₁ и P₂ , Т₁(n) имеет степень роста O(f(n)), a Т₂(n) – O(g(n)). Тогда время последовательного выполнения фрагментов P₁ и P₂ имеет степень роста O(max(f(n) ,g(n))). Чаще всего данное правило используется для оценки времени выполнения последовательности операторов.

2. Время выполнения операторов присваивания, чтения и записи обычно имеет порядок O (1).

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

4. Рекурсивная функция имеет порядок O (nLog(n)).

Порядок выполнения работы

1. Для выполнения работы использовать функцию f(n), реализованную в ходе выполнения лабораторной работы №1 (функции № 5-14).

2. В соответствии с правилами, представленными выше оценить порядок вычислительной сложности О (f(n)).

3. Реализовать программу на С++ и в пакете Maple, которая «засекает» время выполнения функции f(n), при этом каждый раз осуществляя увеличение объема обрабатываемых данных на приращение k.

4. C помощью программы разработанной п. 3 провести серию экспериментов и получить экспериментальную зависимость T_f(n)(n) для функций выбранной в п. 1 и построить график этой зависимости.

5. Произвести сопоставление эмпирических и теоретических данных. Сделать выводы о проделанной работе.

Приложение 1: Вид графического интерфейса и исходный текст программы к лабораторной работе №2

Приложение №1

Вид графического интерфейса и исходный текст программы

к лабораторной работе №2

Рисунок 2 Вид программы, осуществляющей оценку вычислительной сложности алгоритма

Исходный текст программы:

//---------------------------------------------------------------------------

#include <vcl.h>

#pragma hdrstop

#include <dos.h>

#include <iostream.h>

#include "Unit1.h"

#include "dstring.h "

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma resource "*.dfm"

TForm1 *Form1;

//---------------------------------------------------------------------------

int n0,n1,sum,T0,Tk,step,i,k,j;

long double T,n;

struct time t1,t2;

__fastcall TForm1::TForm1(TComponent* Owner)

: TForm(Owner)

{

}

//---------------------------------------------------------------------------

void __fastcall TForm1::ClearGridValues(TStringGrid *Grid)

{ int p,r,s,t;

p=Grid->RowCount;

r=Grid->ColCount;

for(s=1; s<p; s++)

for(t=0; t<r; t++)

Grid->Cells[t][s]="";

}

//---------------------------------------------------------------------------

void __fastcall TForm1::Button1Click(TObject *Sender)

{ ClearGridValues(StringGrid1);

n0=StrToFloat(Edit1->Text);

n1=StrToFloat(Edit2->Text);

step=StrToFloat(Edit3->Text);

StringGrid1->RowCount = n1-n0;

int l=0;

Form1->Series1->Clear();

for(n=n0; n<=n1;n=n+step )

{ l++;

//-----------------------------------------------------------//

if (RadioButton1->Checked)

{gettime(&t1);

sum=0;

for(int i=0; i<n; i++)

sum++;

gettime(&t2); }

//-----------------------------------------------------//

if (RadioButton2->Checked)

{gettime(&t1);

sum=0;

for(int i=0; i<n; i++)

for(int k=0; k<n; k++)

sum++;

gettime(&t2); }

//-----------------------------------------------------//

if (RadioButton3->Checked)

{gettime(&t1);

sum=0;

for(i=0; i<n; i++)

for(j=0; j<n*n; j++)

sum++;

gettime(&t2); }

//-----------------------------------------------------//

if (RadioButton4->Checked)

{gettime(&t1);

sum=0;

for(i=0; i<n; i++)

for(j=0; j<i; j++)

sum++;

gettime(&t2); }

//-----------------------------------------------------//

if (RadioButton5->Checked)

{gettime(&t1);

sum=0;

for(i=0; i<n; i++)

for(j=0; j<i*i; j++)

for(k=0; k<j; k++)

sum++ ;

gettime(&t2); }

//-----------------------------------------------------//

if (RadioButton6->Checked)

{gettime(&t1);

sum=0;

for(i=1; i<n; i++)

for(j=1; j<i*i; j++)

if (j% i==0)

for(k=0; k<j; k++)

sum++;

gettime(&t2); }

//-----------------------------------------------------//

//Вычисление начального и конечного времени в mS //

T0=t1.ti_hour*360000+t1.ti_min*6000+t1.ti_sec*100+t1.ti_hund;

Tk=t2.ti_hour*360000+t2.ti_min*6000+t2.ti_sec*100+t2.ti_hund;

T=Tk-T0;

Form1->Series1->AddXY(n,T,FloatToStr(n),clRed);

StringGrid1->Cells [0][l] = FloatToStr(n)+".";

StringGrid1->Cells [1][l] = FloatToStr(T);

StringGrid1->Cells [2][l] = IntToStr(t1.ti_hour)+":"+IntToStr(t1.ti_min)

+":"+IntToStr(t1.ti_sec)+"."+FloatToStr(t1.ti_hund);

StringGrid1->Cells [3][l] =IntToStr(t2.ti_hour)+":"+IntToStr(t2.ti_min)

+":"+IntToStr(t2.ti_sec)+"."+FloatToStr(t2.ti_hund);

}

}

//---------------------------------------------------------------------------

void __fastcall TForm1::RadioButton1Click(TObject *Sender)

{ AnsiString p;

p="sum=0; \r\n"

"for(i=0;i<n;i++)\r\n "

"sum++ ;" ;

Memo1->Text="";

Memo1->Text=p ;

}

//---------------------------------------------------------------------------

void __fastcall TForm1::RadioButton2Click(TObject *Sender)

{

Memo1->Text="";

Memo1->Text="sum=0;\r\n"

"for(i=0; i<n; i++)\r\n"

" for(j=0; j<n; j++)\r\n"

" sum++ ;" ;

}

//---------------------------------------------------------------------------

void __fastcall TForm1::RadioButton3Click(TObject *Sender)

{

Memo1->Text="";

Memo1->Text="sum=0;\r\n"

"for(i=0; i<n; i++)\r\n"

" for(j=0; j<n*n; j++)\r\n"

" sum++; " ;

}

//---------------------------------------------------------------------------

void __fastcall TForm1::RadioButton4Click(TObject *Sender)

{

Memo1->Text="";

Memo1->Text="sum=0;\r\n"

"for(i=0; i<n; i++)\r\n"

" for(j=0; j<i; j++)\r\n"

" sum++; " ;

}

//---------------------------------------------------------------------------

void __fastcall TForm1::RadioButton5Click(TObject *Sender)

{

Memo1->Text="";

Memo1->Text="sum=0;\r\n"

"for(i=0; i<n; i++)\r\n"

" for(j=0; j<i*i; j++)\r\n"

" for(k=0; k<j; k++)\r\n"

" sum++ ;" ;

}

//---------------------------------------------------------------------------

void __fastcall TForm1::RadioButton6Click(TObject *Sender)

{

Memo1->Text="";

Memo1->Text="sum=0;\r\n"

"for(i=0; i<n; i++)\r\n"

" for(j=0; j<i*i; j++)\r\n"

" if (j% i==0)\r\n"

" for(k=0; k<j; k++)\r\n"

" sum++; " ;

}

//---------------------------------------------------------------------------

void __fastcall TForm1::FormCreate(TObject *Sender)

{

StringGrid1->Cells[0][0]="N";

StringGrid1->Cells[1][0] ="T(N)";

StringGrid1->Cells[2][0] ="начало в:";

StringGrid1->Cells[3][0] ="конец в:";

Memo1->Text="";

RadioButton1Click(RadioButton1);

}