8/13/2019 Estimarea Timpului Cerut de Algoritm
1/12
Algoritmi
Estimarea timpului cerut de algoritm
8/13/2019 Estimarea Timpului Cerut de Algoritm
2/12
Ce reprezinta timpul cerut de
algoritm?
T(n) este timpul necesar executariialgoritmului. De obicei , in acest timp
nu se include durata operatiilor de
introducere a datelor initiale si deextragere a rezultatelor.
8/13/2019 Estimarea Timpului Cerut de Algoritm
3/12
n procesul implementrii practice a oricrui algoritm apare necesitateaestimrii timpului de execuie T(n) pnla testarea i depnarea definitiv a
programului ce-l realizeaz.
S-a ajuns la concluzia ca prin metode teoretice este foarte greu de determinat
o expresie exacta pentru T(n). Din aceste motive se cauta o limita superioara
timpului cerut de algoritm.
Presupunem , n scopuri didactice c execuia oricrui operator Pascal (+,-,/,*,div,and,
8/13/2019 Estimarea Timpului Cerut de Algoritm
4/12
Admitem c ntr-o expresie E apar
m operatori Pascal i k apeluri alefunciei F. Evident , numrul QEdeoperaii elementare necesare pentru
calcularea expresiei E se determinca QE=m+kQF unde QF este
numrul de operaii elementarenecesare pentru calcularea funciei F.
8/13/2019 Estimarea Timpului Cerut de Algoritm
5/12
Exemple
Expresia E
a*b+c
(ad)
sin(x)+cos(y)
a+M[i]
sin(x+y)+sin(x-y)
Nr de operaiielementare
2
3
1+Qsin+Qcos
2
3+2Qsin
8/13/2019 Estimarea Timpului Cerut de Algoritm
6/12
Numrul de operaii elementare necesare pentru execuia unei
insruciuniPascal
8/13/2019 Estimarea Timpului Cerut de Algoritm
7/12
Pentru exemplificare vom estima numrul de operaii elementare Q(n) necesareordonrii elementelor unui vector prin metoda bulelor.
ProcedureSortare(varA:Vector; n:integer);
Vari,j :integer;R:real;
{1} Begin
{2} Fori:=1ton do
{3} Forj:=1 ton-1 do{4} IfA[j]>A[j+1] then
{5} Begin
{6} r:=A[j];
{7} A[j]:=A[j+1];
{8} A[j+1]:=r;End;
End; {Sortare}
8/13/2019 Estimarea Timpului Cerut de Algoritm
8/12
Instruciunile I1,I2,...,I8ale procedurii Sortare vor fireferite cu ajutorul comentariilor {1},{2},...,{8} din
partea stnga liniilor de program. Prin Qjvom notanumrul de operaii elementare necesare pentruexecutarea instruciunii Ij:Q6= 2;
Q7= 4;
Q8= 3;
Q5= Q6+ Q7+Q8+1=10;
Q4= 4+Q
5+1=15;
Q3 =0+1+(n-1)Q4+(n-1)+1=16n-14;
Q2= 0 + 0 + nQ3 + n + 1=16n2-13n+1;
Q1=Q2+1=16n2-13n+2
8/13/2019 Estimarea Timpului Cerut de Algoritm
9/12
Q1+Q2+Q3+Q4+Q5+Q6+Q7+Q8= Q(n) = 16n2-13n+2
T(n) = (16n2
-13n+2)
Rezultate
8/13/2019 Estimarea Timpului Cerut de Algoritm
10/12
Ordinea parcurgerii instructiunilor
Este impusa de structura
programelor PASCAL. Evident ,
mai intii se nalizeaza
instructiunile simple , iar apoi
cele structurate.
8/13/2019 Estimarea Timpului Cerut de Algoritm
11/12
Expresiile analitice T(n) obinute n rezultatul analizeiprogramelor PASCAL pot fi folosite pentru determinarea
experimental a timpului necesar efecturii uneioperaii elementare. De exemplu , pentruprocedurasortare n=10000 i T(n)=28,18 s. Din ecuaia
( 16n2-13n+2) .=28,18 obinem 1,8*10-8secunde.
Evident, aceast valoare este valabil numai pentrumediul de programare Turbo Pascal 7.0 i calculatorulPentium cu frecvena ceasului de sistem de 500 Mhz,
utilizate n procesul de msurare a timpului de execuie aprocedurii Sortare.
8/13/2019 Estimarea Timpului Cerut de Algoritm
12/12
Au realizat :Soltan Vasile
Rosca Valentina