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.