Universitatea Tehnic a Moldovei
Facultatea Calculatoare, Informatic i Microelectronic
Catedra Tehnologii Informaionale
RAPORT
Analiza si Poiectarea Algoritmilor
Lucrarea nr.1
Tema: Analiza algoritmilor (Timpul de execuie al algoritmilor).
A efectuat:
[Link]. TI-142
A verificat:
Bagrin Veronica
Chiinu 2015
[Link] LUCRRII
1.1
1.2
1.3
Analiza empiric a algoritmilor.
Analiza teoretic a algoritmilor.
Determinarea complexitii temporale i asimptotice a algoritmilor
[Link] LUCRRII
Fie irul lui Fibonacci definit prin urmtoarea recuren:
i se propun urmtorii algoritmi de generare a acestui ir:
[Link] de-al n-lea termen al irului se poate obine direct din definiie:
function fib1(n)
if n < 2 then return n
else return fib1(n-1) + fib1(n-2)
[Link] iterativ:
function fib2(n)
i 1; j 0
for k 1 to n do j i + j
ij-i
return j
3.i al treilea algoritm algoritm :
function fib3(n)
i 1; j 0; k 0; h 1
while n > 0 do
if n este impar then t jh
j ih+jk+t
i ik+t
2
t h
h 2kh+t
k k2+t
n n div 2
return j
[Link] 4 algoritm:
function fib4(4)
int fib(int x)
{
return 1/sqrt(5)*(pow((1+sqrt(5))/2,x)-pow((1-sqrt(5))/2,x));
}
[Link] DE BAZ
3.1 Efectuai analiza empiric a algoritmilor propui.
3.2 Determinai relaia ce determin complexitatea temporal pentru aceti algoritmi.
3.3 Determinai complexitatea asimptotic a algoritmilor.
3.4 Facei o concluzie asupra lucrrii efectuate.
3.1 Analiza empiric a algoritmilor propui.
Metrica de analiza a complexitii algoritmilor propui va fi numrul de operaii efectuate.
Tab.1
Algoritmi:
n=
10
20
30
35
40
fib1/
operaii
55
6765
832040
9227465
102334155
fib2/
operaii
fib3/
operaii
55
6765
832040
9227465
102334155
55
6765
832040
9227465
102334155
fib 4/
operatii
55
6765
832040
9227465
102334155
3.2 Determinarea relaiei ce determin complexitatea temporal pentru aceti algoritmi i determinarea
complexitii asimptotice a algoritmilor.
Pentru alg.1 :
function fib1(n)
(1) if n < 2 then return n
(2)
else return fib1(n-1) + fib1(n-2)
Pentru acest algoritmul conteaz dimensiunea datei de intrare deoarece fiind un algoritm recursiv cu
apeluri care se suprapun (se repet) pentru dimensiuni mari ale datelor de intrare (de ex. n>50) se
produce o suprancrcare a stivei (resurse mari de memorie) i n rezultat se va bloca execuia
programului.
Timpii de rulare pentru instruciunile if then (1) , este suma dintre cel pentru evaluarea condiiei,
O(1) i cel al secvenei ce se execut la condiie adevrat, tot O(1), iar n cazul evaluarea condiiei este
fals atunci pentru (2) avem un apel recursiv al algoritmului care reprezint o recuren liniar
omogen de forma:
, n2
iar
.Putem s rescriem aceast recuren sub forma
=0
care are ecuaia caracteristic
cu rdcinile
=(1
) / 2.
Soluia general are forma
Impunnd condiiile iniiale, obinem
de unde determinm
=1/
Deci,
= 1/
). Observm c
==(1+
)) / 2,
i obinem
= 1/
).
Nu prezint nici o dificultate s artm acum c timpul pentru algoritmul fib1 este n (
Listingul programului :
#include <stdio.h>
#include <conio.h>
#include <time.h>
int cont=0;
int fib(int n);
main()
{
time_t start,end;
int i,x;
double dif;
do
{
printf("n=");
scanf("%d",&i);
time (&start);
cont=0;
x=fib(i);
time (&end);
dif = difftime (end,start);
printf("rezultat: %d\n",x);
printf("timp de executie: %.2lf secunde\n\n",dif);
printf("Iteratie: %d\n",cont);
}while(i);
getch();
return 0;
}
int fib(int n)
{
if (n<2) {cont++;return n;}
else {cont++;return fib(n-1)+fib(n-2);}}
Rezultatul programului:
).
Pentru alg. 2:
function fib2(n)
(1) i 1; j 0
(2) for k 1 to n do
(3)
ji+j
return j
Linie
ij-i
Cost operaie
Repetri
2* (n+1)
Calcularea costului total :
T(n)=2 + [2* (n + 1)] * 1 + 2 * n = 2 + 2 * n + 2 + 2 * n=4 * n + 4
Se deduce imediat c timpul pentru fib2 este n (n), deoarece avem ca barometru ciclul for (2) care
necesit n iteraii.
Listingul programului:
#include <stdio.h>
#include <conio.h>
6
#include <time.h>
int cont=0;
int fib(int n);
main()
{
time_t start,end;
int i,x;
double dif;
do
{
printf("n=");
scanf("%d",&i);
time (&start);
cont=0;
x=fib(i);
time (&end);
dif = difftime (end,start);
printf("rezultat: %d\n",x);
printf("timp de executie: %.2lf secunde\n\n",dif);
printf("Iteratie: %d\n",cont);
}while(i);
getch();
return 0;
}
int fib(int n)
{
int i=1,j=0,k;
for (k=0;k<n;k++)
{
j=i+j;
i=j-i;
cont+=2;
}
return j;
}
Pentru alg. 3:
function fib3(n)
(1) i 1; j 0; k 0; h 1
(2) while n > 0 do
(3)
if n este impar then
(4)
t jh , j ih+jk+t, i ik+t
2
(5)
t h ,h 2kh+t, k k2+t
(6)
n n div 2
return j
Linie
Cost operaie
Repetri
(Log n) + 1
Log n
Log n
Log n
Log n
Calcularea costului total:
T(n)=4 + log n + 1 + log n + 3 * log n + log n + log n=7 * log n + 5
8
Pentru a analiza fib3, lum ca barometru instruciunile din bucla while (2). Fie
sfritul executrii celei de-a t-a bucle. n particular,
valoarea lui n la
=[n/2] , unde [] este partea ntreag a
numarului. Dac 2 tm, atunci
=[
Deci
Fie m=1 + [
] ] n/
]. Deducem:
n/
Dar,
N, i deci,
<1
=0, care este condiia de ieire din bucl. Cu alte cuvinte, bucla se execut de
cel mult m ori, timpul lui fib3 fiind n O(log n).
Listingul programului :
#include <stdio.h>
#include <conio.h>
#include <time.h>
int cont=0;
int fib(int n);
main()
{
time_t start,end;
int i,x;
double dif;
do
{
printf("n=");
scanf("%d",&i);
time (&start);
cont=0;
x=fib(i);
time (&end);
9
dif = difftime (end,start);
printf("rezultat: %d\n",x);
printf("timp de executie: %.2lf secunde\n\n",dif);
printf("Iteratie: %d\n",cont);
}while(i);
getch();
return 0;
}
int fib(int n)
{
int i=1,j=0,k=0,h=1,t;
while (n>0)
{
if (n%2!=0)
{
t=j*h;
j=i*h+j*k+t;
i=i*k+t;
cont+=3;
}
t=h*h;
h=2*k*h+t;
k=k*k+t;
n=n/2;
cont+=4;
}
return j;
}
10
Pentru alg 4 :
function fib4(x)
int fib(int x)
{
return 1/sqrt(5)*(pow((1+sqrt(5))/2,x)-pow((1-sqrt(5))/2,x));
}
Listingu programului:
#include <stdio.h>
#include <conio.h>
#include <time.h>
int cont=0;
int fib(int x);
main()
{
time_t start,end;
int i,x;
double dif;
do
{
printf("n=");
scanf("%d",&i);
11
time (&start);
cont=0;
x=fib(i);
time (&end);
dif = difftime (end,start);
printf("rezultat: %d\n",x);
printf("timp de executie: %.2lf secunde\n\n",dif);
printf("Iteratie: %d\n",cont);
}while(i);
getch();
return 0;
}
int fib(int x)
{
cont++;return 1/sqrt(5)*(pow((1+sqrt(5))/2,x)-pow((1-sqrt(5))/2,x));
}
Tabelul pentru iteratii:
n
Fib1/IT
Fib2/IT
Fib3/IT
10
177
20
22
20
21891
40
26
30
2682537
60
32
12
35
29860703
70
33
40
331160281
80
30
Fib4/IT
Tabelul pentru timp:
n
10
Fib1/Timp
0.00
Fib2/Timp
0.00
Fib3/Timp
0.00
Fib4/Timp
0.00
20
0.00
0.00
0.00
0.00
30
0.00
0.00
0.00
0.00
35
1.00
0.00
0.00
0.00
40
1.00
0.00
0.00
0.00
Graficile pentru iteratii ale celor 4 forme fibonace:
Graficile pentru timp ale celor 4 forme fibonace:
13
Concluzie:
La elaborarea acestei lucrri am observat c timpul de
funcionare a programului este direct proporional cu
complexitatea algoritmilor i timpul de elaborare este invers
proporional, adic dac dorim algoritmi uor de neles, de
depanat vom alege un algoritm mai simplu dar pentru care
vom plti timp mai mare de execuie, i invers, pentru un
algoritm mai perfomat vom ctiga timp de execuie dar se
va cheltui mai mult timp pentru elaborare, depanare etc.
Conformp algoritmului unu observam ca atit din punct de
vedere a iteratiilor cit si a timpului iese in evidenta fata de
cele lalate [Link] ce creste numarul pe care il dam
creste foarte semnificativ numarul de iteratii cit si timpu de
[Link] pina la numarul 35 timpul de executie este
constan 0 dupa 35 timpu de executie devine mai
greu,incepind cu 50 timpu de executie se efectuiaza intr-un
timp [Link] algoritmul doi observam deja o
compexitate mai mare din punct de vedere a programului si o
simplitate din partea rezultatului [Link] dindu-i un
numar din zece in zece observam ca iteratiile variaza din 20
in 20 si timpul de executie este 0 adica se executa cu o viteza
foarte rapida .Algoritmul 3 este si mai complex din punct de
14
vedere a programului,iteratiile de la un interval la altu variaza
si mai putin si la fel timpul de executie este [Link] algoritmul 4
iese in evidenta faptul ca la orice numar oferit numarul de
iteratii este egal cu 1 si asta datorita faptului ca este doar o
singura formula si viteza de executie fiind foarte mare.
15