Analiza algoritmilor. Masurarea volumului
-
Upload
colegiul-de-industrie-usoara -
Category
Education
-
view
873 -
download
5
Transcript of Analiza algoritmilor. Masurarea volumului
Analiza algoritmilor
Complexitatea algoritmilor
Algoritmul reprezintă o succesiune finită de operaţii cunoscute care fiind executate într-o ordine bine stabilită furnizează soluţia unei probleme.
Complexitatea algoritmilor
Coplexitatea algoritmilor se caracterizează prinnecesarul de memorie şi durata de execuţi.
Metodele de estimare a acestor indicatori se studiază într-un compartiment special al informaticii numit analza algoritmilor.
Complexitatea algoritmilor
Vom folosi următoarele notaţii:
n- un număr natural ce caracterizează mărimea datelor de intrare ale unui algoritm.
V(n)-volumul de memorie internă necesară pentru păstrarea datelor cu care operează algoritmul.
T(n)- timpul execuţiei algoritmului.
Complexitatea algoritmilor
Exemplu, pentru rezolvarea unei probleme există doi algoritmi pe care îi notăm cu А1 şi А2
Necesarul de memorie şi timpul execuţiei pentru algoritmul este А1
V1 (n)=100n2+4T1(n)=n3+10-3
Iar А2
V2 (n)=100n+12
T2(n)=2n•10-6
Complexitatea algoritmilor
n 10 20 30 40 50
V1(n) 9,77Kocteţi 39,06 Kocteţi
87,89 Kocteţi
156,25 Kocteţi
244,14 Kocteţi
V2(n) 112 Kocteţi 212 Kocteţi 312 Kocteţi 412 Kocteţi 512 Kocteţi
T1(n) 1s 8s 9s 16s 25s
T2(n) 0,001s 1,05s 18s 13zile 36ani
Estimarea necesarului de memorie
Evaluarea necesarului de memorie V(n) poate fi făcută calculînd numărul variabilelor nestructurate integer,real,booleean,char,enumerare,subdomeniu..
În PASCAL 7 memoria se alocă conform tabelului
Tip Memoria
integer 2 octeţi
real 6 octeţi
boolean 1 octet
char 1 octet
enumerare 1 octet
interval In dependenţă de tipul de bază
referinţă 4 octeţi
pointer 4 octeţi
Var A:array[1..n,1..n] of real;
B :array [1..n] of integer;
P: boolean;
S:string[10];
Sa calculam necesarul de memorie pentru variabilele A,B,P,S
V(n)=6n2 +n+1+10= 6n2 +n+11 octeti
exercitiu
Sa se calculeze necesarul de memorie pentru variabilele din urmatoarele declaratii
Var A:array[1..n,1..n] of integer;
B :string;
P: boolean;
C:array[1..n,1..n,1..n] of boolean;
Masurarea timpului de executie
Unit U7;InterfaceFunction TimpulCurent:real;ImplementationUses Dos;Var ore:word;
minute:word; secunde:word; sutimi:word;
Function TimpulCurent;GetTime(ore,minute,secunde,sutimi);TimpulCurent:=3600.0*ore+60.0*minute+1.0*secunde+0.01*sutimi;End;End.
Masurarea timpului de executie
Program p149;Uses U7;Type vector =array[1..10000] of real;Var A:vector;i,n:integer;t1,t2:real;procedure sortare (var A:vector;n:integer);var I,j:integer;r:real;begin for i:=1 to n do for j:=1 to n-1 do
if A[j]>A[j+1] thenbeginr:=A[j];
A[j]:=A[j+1];A[j+1]:=r;End;End;BeginWrite(‘Introduceti numarul de elemente n=’);Readln(n);For i:=1 to n do A[i]:=n-i+1;t1:=TimpulCurent;sortare(A,n);t2:=TimpulCurent;writeln(‘Timpul executiei ’, (t2-t1):7:2, ‘sek.’);readln.