–PAGE_BREAK–Входные данные
Входными данными для моей работы является начальное число вершин графа, которое по мере работы программы увеличиться на 30 верши. Это число не может превосходить значения 80 вершин, так как в процессе работы программы число увеличивается на 30 и становиться 110 – это «критическое» число получается из расчета 110
»
216/3
. Это происходит потому, что стандартный тип
int
не может вместить в себя более чем
216
. Мне же требуется для нормально работы программы, чтобы тип вмещал в себя утроенное количество вершин неориентированного графа. Конечно, это всего лишь приближение, но с учётом того, что графы генерируются случайно возможность набора 33000 невелико и, следовательно, допустимо.
Входной файл генерируется каждый раз новый.
Графы для расчета мультипликативных констант генерируются случайным образом, используя датчик случайных чисел, это-то и накладывает ограничения на количество вершин. Дело в том, что при работе с генератором случайных чисел предпостительно иоспользовать целый тип данных – так говорил товарищ Подбельский В.В.
Оценка временной сложности.
Каткие сведения о временной сложности.
Качество алгоритма оценивается как точность решения и эффективность алгоритма, которая определяется тем временем, которое затрачивается для решения задачи и необходимым объёмом памяти машины.
Временная сложность алгоритма есть зависимость от количества выполняемых элементарных операций как функция размерности задачи. Временная сложность алгоритма А обозначается .
Размерность задачи – это совокупность параметров, определяющих меру исходных данных. Временная оценка алгоритма бывает двух типов:
1.
априорная – асимптотическая оценка сложности
2.
апосториорная – оценка сложности алгоритма с точностью до мультипликативных констант, сделанных для конкретной машины.
Именно асимптотическая оценка алгоритма определяет в итоге размерность задачи, которую можно решить с помощью ЭВМ. Если алгоритм обрабатывает входные данные размера N
за время CN2
, где С – некая постоянная, то говорят, что временная сложность этого алгоритма есть . Вернее говорить, что положительная и нулевая функция есть , если существует такая постоянная С, что для всех отрицательных значений N.
Вычисление временной сложности.
Для того, чтобы проверить правильность временной оценки алгоритма, надо знать априорную оценку сложности.
Проверка вычислительной сложности алгоритма сводиться к экспериментальному сравнению двух или более алгоритмов, решающих одну и ту же задачу. При этом возникают две главные проблемы: выбор входных данных и перевода результатов эксперимента в графики кривых сложности.
При прогоне программы мы получаем значения функции, которые можно изобразить на графике как функцию f(
NX,NY,NZ
)
. Данные точки показывают характер кривой. Для аппроксимации этого облака точек в своей курсовой работе я использовал метод наименьших квадратов.
Анализ по методу наименьших квадратов заключается в определении параметров кривой, описывающих связь между некоторым числом N
пар значений Xi, Yi(
в данном случае nи t
соответственно), обеспечивая при этом наименьшую среднеквадратичную погрешность. Графически эту задачу можно представить следующим образом – в облаке точек Xi, Yi
плоскости XY(
смотри рисунок) требуется провести прямую так, чтобы величина всех отклонений отвечала условию:
N
F =
K=1
Где
В моём случае
T(NX,NY,NZ)=O(NX*(NY+NZ) =>
T(NX,NY,NZ)=C1*NX*(NY+NZ)+C2*(NY+NZ)+C3*(NY)+C4*(NZ)
Следовательно для моего примера мы получим:
Для того чтобы получить значение функции на
K-
том эксперименте, мы засекаем значение времени перед вызовом функции, которая реализует алгоритм, вставим оператор вида:
TikTak=clock();
Где функция
clock()
даёт время с точностью до нескольких миллисекунд (в языке С++ она описана в заголовочном файле
time.h)
. После выполнения процедуры, реализует алгоритм, мы находим разность времени
TikTak=cloc() — TikTak;
После всех проделанных манипуляций нужно прировнять к нулю все частные производные. Это будет выглядеть, в общем виде, примерно так:
После раскрытия скобок и замены T(n)=T(n)=(c,
t
(n))=
получим
Положим А
ij=(ti, tj)
и
B=(ti,TikTak)
=
>
мы получили систему уравнений
AX=B
, где Х=С. Формирование в матрице столбцов А и столбцов В записывается очень легко используя любой алгоритмический язык. После заполнения матрицы её остаётся решить и вывести решения этой задачи. Решение производиться методом Жордана.
Априорная временная оценка процедур.
Процедура вывода графа на экран в последовательном представлении:
Void prin3(Array *X, int N1, int N)
X – граф в связаном представлении
N – количество вершин графа.
продолжение
–PAGE_BREAK–N1 – количество дуг в графе Х O(N,N1)=N*N1
Процедура вывода графа на экран в связаном представлении:
Void print3(Spisok **X, int N)
X – граф в связаном представлении
N – количество дуг в графе.
O(N)=N
Процедура вычисления разности графов
с возвращающим значением последовательного графа:
Array * RaznostZ(int n, int &n1, Array *X, Spisok **Y,Array *Z)
N — количество дуг графа
N1 – количество вершин в графе Х
X – грав в последовательном представлении
Y — грав в связаном представлении
Z – грав в последовательном представлении
O(N,N1)=N1*N*k=N1*N2
N2 – количество вершин в графе Y
Процедура
вычисления разности графов
с возвращающим значением последовательного графа:
Spisok * RaznostY(int n, int &n1, Array *X, Spisok **Y)
N — количество дуг графа
N1 – количество вершин в графе Х
X – грав в последовательном представлении
Y — грав в связаном представлении
O(N,N1)=N1*N*(k+l)=N1*(N3+N2)
N2 – количество вершин в графе Y
N3 – количество вершин в графе Z – возвращаемом.
Процедура
ввода графов
в последовательном представлении:
Spisok **ReadFileY( Spisok **Y, char *st)
St – указатель на строку с именем файла из которого будет происходить ввод
Y — грав в связаном представлении
O(N,N1)=N+N2
N2 – количество вершин в графе Y
Процедура
ввода графов
в последовательном представлении:
Array *ReadFileY( Array *X, char *st)
St – указатель на строку с именем файла из которого будет происходить ввод
X – грав в последовательном представлении
O(N,N1)=N2
N2 – количество вершин в графе X
Текст программы.
# include
# include
# include
# include
# include
# include
///////////////////////////////////////////////////////////////////////////////////////////////////////
struct Spisok //Связанное представление графа
{ int index; //Содержвтельная «ячейка»
Spisok *next;//Следуюцая «дуга»
};
///////////////////////////////////////////////////////////////////////////////////////////////////////
struct Array //Последовательное представление графа
{ int I; //из какой вершины
int J; //в какую вершину
};
///////////////////////////////////////////////////////////////////////////////////////////////////////
inline double fun1(double N_X,double N_Y,double N_Z){ return N_X*(N_Y+N_Z);}
inline double fun2(double N_X,double N_Y,double N_Z){ return N_X+N_Y;}
inline double fun3(double N_X,double N_Y,double N_Z){ return N_X;}
inline double fun4(double N_X,double N_Y,double N_Z){ return N_Y;}
inline double fun5(double N_X,double N_Y,double N_Z){ return N_Z;}
inline double fun6(double N_X,double N_Y,double N_Z){ return 1;}
///////////////////////////////////////////////////////////////////////////////////////////////////////
const int N = 6, M = N+1;
double A[N][M];
double B[N][M];
typedef double(*MENU1)(double,double,double);
MENU1 MyMenu[6] = { fun1,fun2,fun3,fun4, fun5,fun6 };
////////////////////////////////////////////////////////////////////////////////
int gordanA(int n, int m)
{ int i, j, k, ir;
double s, c;
for (j = 0; j
for (s = 0, i = 0; i fabs(s)) s = A[ir = i][j];
if(s==0)return -1;
for (k = j + 1; k
c = A[ir][k]/s;
for (i = 0; i
for (i = ir + 1; i
A[n — 1][k] = c;
}
}
return 0;
}
///////////////////////////////////////////////////////////////////////////////
long double Stp(int a, int n)
{
long double c,bi;
int k;
c=1;
k=n;
bi=a;
while(k>0){
if(k%2==1)c*=bi;
bi*=bi;
k/=2;
}
return c;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////
void CursorOff(void)
{asm{
mov ah,1
mov ch,0x20
int 0x10
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////
Spisok **GenSeY(int Mas_y,int & Counter)
{ Counter=0;
Spisok **Y = new Spisok* [Mas_y];
for (int i = 0; i
int m = 0;
int *Pro = new int [Mas_y];
Spisok *beg = NULL, *end = NULL ;
for (int j = 0; j
int k = random(Mas_y);
int flag = 0;
for (int j = 0; j
if (k != 0 && flag == 0){
Pro[m] = k;
m++;
if ((beg==NULL) && (end==NULL)){
end=new(Spisok);
if (end == NULL) {cout
beg=end;
}
else{
end=end->next=new (Spisok);
if (end==NULL) {cout
}
end->next=NULL;
end->index = k;
Counter++;
}
}
Y [i] = beg;
delete [] Pro;
}
return Y;
}
////////////////////////////////////////////////////////////////////////////////
Array *GenSeX(int Mas_y,int & Counter)
{ Counter=0;
Array *X = new Array[Mas_y*Mas_y];
if(X==NULL){cout
randomize();
for (int i = 0; i
int m = 0;
int *Pro = new int [Mas_y];
for (int j = 0; j
int k = random(Mas_y);
int flag = 0;
for (int j = 0; j
if (k != 0 && flag == 0){
X[Counter].I=i;
X[Counter].J=k;
Pro[m] = k;
m++;
Counter++;
}
}
delete [] Pro;
}
return X;
}
////////////////////////////////////////////////////////////////////////////
int Number(int & kol2,char *st )
{ int N;
ifstream file;
int kol1 = 0; kol2 = 0;
file.open(st);
if (!file) cerr
else
{file >> N;
file.get();
for( int i = 0; i
{char *string = new char[3*N];
file.getline(string,3*N,’\n’);
for( int j = 0; string[j] != ‘0’; j++ )
{if (string[j] == ‘ ‘)
//{if((j%2!=0)||(j > N*3))
// {cout
if (i
else kol2 ++;
}
delete [] string;
}
}
file.close();
//cout
return kol1;
}
////////////////////////////////////////////////////////////////////////////////
Array *ReadFileX(Array *X,char * st )
{
ifstream file;
int n;
file.open(st);
if (!file) cerr
else
{file >> n;
file.get();
int k = 0,n1=0;
for(int i=0; i
file >> n1;
while (n1 != 0){
X[k].I = i;
X[k].J = n1-1;
k++;
n1=0;
file >> n1;
//cout
}
}
}
file.close();
return X;
}
////////////////////////////////////////////////////////////////////////////////
Spisok **ReadFileY(Spisok **Y,char *st )
{
int n;;
ifstream file;
file.open(st);
if (!file) cerr
else
{file >> n;
file.get();
for(int i=0; i
{
char *string = new char[580];
if (string == NULL) {cout
file.getline(string,580,’\n’);
delete [] string;
}
for(int j=0; j
{
int n1;
file >> n1;
Spisok *beg=NULL,*end = NULL;
while (n1 != 0)
{ if ((beg==NULL) && (end==NULL))
{ end=new(Spisok);
if (end == NULL) {cout
beg=end;}
else
{ end=end->next=new (Spisok);
if (end==NULL) {cout
end->next=NULL;
end->index = n1-1;
file >> n1;
}
//file >> n1;
Y[j] = beg; }
}
file.close();
return Y;
}
////////////////////////////////////////////////////////////////////////////////
void print3(Array *X,int N1,int N)
{
int k = 0;
for ( int i = 0; i
cout
for (k=0; k
}
}
////////////////////////////////////////////////////////////////////////////////
void print2(Spisok **X,int N)
{ for (int i=0;i
cout
Spisok *rex = X[i];
while (rex != NULL){
cout index
rex = rex->next;
}
}
}
////////////////////////////////////////////////////////////////////////////////
void WriteFile(char *st,int Mas_y)
{
ofstream F;
F.open(st);
randomize();
if (!F) cout
F
for (int i = 0; i
{ int m = 0;
int *Pro = new int [Mas_y];
for (int j = 0; j
{int k = random(Mas_y+1);
int flag = 0;
for (int j = 0; j
{if (k==Pro[j]) flag = 1;}
if (k != 0 && flag == 0)
F
Pro[m] = k;
m++;
}
delete [] Pro;
F
}
F.close();
}
////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////
int HowMuch(char *FileName)
{//читаем первую строчку файла и узнаём сколько вершин в графе.
ifstream file;
int n=0;
file.open(FileName);
if (!file) cerr
else file >> n;
return n;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////
Array *RaznostZ(int n,int &n1,Array *X,Spisok **Y,Array *Z)
/*обьединение в последовательном представлении
N — кол-во вершин в новом графе, N2 — кол-во дуг в Y.*/
{float i,j,newn=0;
Array *newX = new Array [n1]; //выделение памяти для графа в последоват представлении
//cout
for(i=0;i
for(j=0;j
if(X[i].I==j){//cout
Spisok *max=Y[j]; //max глядит на начало списка Y[j]
int Flag=0; //Просто флаговая переменная
while(max!=NULL){ //Проверяем на совпадения «входящие» вершины
if(X[i].J==max->index){Flag=1;break;}//если нашли повторение, то выход
max=max->next; //передвигаемся на следующий элемент списка
}
if(Flag==0){ //если не было совпадений вершин, то… всё понятно:
newX[newn].I=X[i].I;
newX[newn].J=X[i].J;
newn++;
}
//cout
}
//cout
}
//cout
n1=newn;
delete [] Z;
return newX;
}
////////////////////////////////////////////////////////////////////////
void DeleteY(Spisok **Z,int n)
{int i=0;
Spisok *rex;
for(i=0;i
rex=Z[i];
while(rex!=NULL){Z[i]=rex->next;delete rex;rex=Z[i];}
delete Z[i];
}
delete [] Z;
}
////////////////////////////////////////////////////////////////////////////////
Spisok** RaznostY(int n,int n1,Array *X, Spisok **Y)
{/*Расчет разности графов Z=X-Y
Z,Y — связанном представлении, X — в последовательном.
n — кол-во вершин графа, n1 — кол-во дуг графа*/
int i,j;
Spisok **Z = new Spisok *[n];//выделение памяти для графа в связанном представлении
for (i=0;i
//cout
for(i=0;i
for(j=0;j
if(X[i].I==j){//cout
Spisok *max=Y[j]; //max глядит на начало списка Y[j]
int Flag=0; //Просто флаговая переменная
while(max!=NULL){ //Проверяем на совпадения «входящие» вершины
if(X[i].J==max->index)Flag=1;//если нашли повторение, то выход
max=max->next; //передвигаемся на следующий элемент списка
}
if(Flag==0){ //если небыло совпадений вершин, то… всё понятно:
Spisok *end=Z[j], *beg=Z[j], *pred=Z[j];
while (end !=NULL) {pred = end ;end = end ->next;}
end = pred;
if((beg==NULL)&&(end==NULL))Z[j]=beg=end=new(Spisok);
else end = end -> next = new (Spisok);
end -> next = NULL;
end -> index = X[i].J;
}
//cout
}
//cout
}
//cout
DeleteY(Y,n); //Убийство связанного графа Игрыка!
return Z;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////
void Demo(void)
/* Х — в последовательном представлении
У — в связанном представлении*/
{ int n=4,N2;
clrscr(); //очистка экрана
CursorOff();
cout
char st [] =«GrapH.txt»; //имя генерируемого файла
cout
WriteFile(st,n); //генерация файла с н вершинами
n=HowMuch(st); //подсчет числа вершин графов
int N1 = Number(N2,st); //подсчет числа дуг
Array *X = new Array [N1]; //выделение памяти для графа в последоват представлении
X = ReadFileX(X,st); //чтение графа в последовательном представлении
cout
print3(X,N1,n); //вывод графа в последовательном представлении
Spisok **Y = new Spisok *[n]; //выделение памяти для графа в связанном представлении
for (int i=0;i
Y = ReadFileY(Y,st); //чтение графа в связанном представлении
cout
print2(Y,n); //печать графа в связанном представлении
Array *Z = new Array[n]; //выделение памяти для графа в последоват представлении
int nZ=N1;
Z=RaznostZ(n,nZ,X,Y,Z);//считаем разность графов: первый параметр — число вершин, второй и третий
//граффы в соответствующем представлении.
cout
print3(Z,nZ,n); //вывод графа в последовательном представлении
//Spisok **Z1 = new Spisok *[n];//выделение памяти для графа в связанном представлении
//for (i=0;i
Y=RaznostY(n,N1,X,Y); //считаем разность графа и записываем это в граф Y
cout
print2(Y,n); //печать графа в связанном представлении
delete [] X; //удаление из памяти графа Х
delete [] Z;
DeleteY(Y,n); //Убийство связанного графа Игрыка!
//DeleteY(Z1,n); //Убийство связанного графа Зюблы!
cout
getch(); //Ждём нажатия любой клавиши
}
////////////////////////////////////////////////////////////////////////////////
void TimeOut(int Tik, float TikTak[], int Mas_x[], int Mas_y[],int Mas_z[])
{
clrscr();
int i=0,j=0,k=0,h=0,count=0;
cout
for(;i
for (k = 0; k
for (i = 0; i
for (int j = 0; j
A[i][N]+=(*MyMenu[i])(Mas_x[k],Mas_y[k],Mas_z[k])*TikTak[k];
}
if(gordanA(N,M))cout
//for(i=0;i
cout
for(i=0;i
cout
double *Mas_Tnz=new double[N];
for(i=0;i
for (int y = 0; y
for (i = 0; i
cout
}
}
////////////////////////////////////////////////////////////////////////////////
void TestTime(int n)
/* Х — в последовательном представлении
У — в связанном представлении
*/
{
clrscr(); //очистка экрана
cerr
int i,nX=0,nZ=0,nY=0;
float TikTak[19],Secundomer=0;
int Mas_x[12],Mas_y[12],Mas_z[12];
for(int Tik=0;Tik
n=n+Tik*5; //количество генерируемых вершин
Array *X = new Array [nX]; //выделение памяти для графа в последоват представлении
X = GenSeX(n,nX); //чтение графа в последовательном представлении
Mas_x[Tik]=nX; //запоминаем кол-во вершин в графе ЫксА
Spisok **Y = new Spisok *[n];//выделение памяти для графа в связанном представлении
for (int i=0;i
Y = GenSeY(n,nY); //чтение графа в связанном представлении
Mas_y[Tik]=nY; //запоминаем кол-во вершин в графе ИгрикА
Array *Z = new Array[n];//выделение памяти для графа в последоват представлении
cerr
cout
nZ=nX; //так надо Сергей Михайловичь
Z=RaznostZ(n,nZ,X,Y,Z);//считаем разность графов: первый параметр — число вершин, второй и третий
//граффы в соответствующем представлении.
//cout
Mas_z[Tik]=nZ; //запоминаем кол-во вершин в графе зЮблА
cout
for(int XXX=0;XXX
cout
Secundomer=clock(); //”… на старт… внимпние… марш!!!” — засекли начала эксперимента.
Y=RaznostY(n,nX,X,Y); //считаем разность графа и записываем это в граф Y
TikTak[Tik]=(clock()-Secundomer);//«Финиш!!!» — получили конец эксперимента
} //к.ц. цикла вовторений
TikTak[Tik]=TikTak[Tik]/(10 * CLK_TCK);//Вычисление тиков!!!
delete [] X; //удаление из памяти графа Х
DeleteY(Y,n); //Убийство связанного графа Игрыка!
delete [] Z;//удаление из памяти графа в последовательном представлении
n-=Tik*5; //«предохраитель» от геометрической прогрессии…
} //к.ц. для экспериментов!!!
//cout
//for (int y = 0; y
cout
getch(); //Ждём нажатия любой клавиши
TimeOut(Tik,TikTak,Mas_x,Mas_y,Mas_z);//вызываем функцию общёта всего и вся
cout
getch(); //Ждём нажатия любой клавиши
}
///////////////////////////////////////////////////////////////////////////
void main (void)
{
Demo();
TestTime(85);
}
///////////////////////////////////////////////////////////////////////////
Тесты.
продолжение
–PAGE_BREAK–