Tehnici avansate de programare

Capitolul 1. Algoritmi. Elemente de analiză a complexităţii algoritmilor

1.1. Algoritmi. Recapitulare

Etapele rezolvării unei probleme cu calculatorul:

1. Analiza problemei

2. Elaborarea algoritmului de rezolvare a problemei / alegerea unui algoritm deja existent

Modalități de descriere a algoritmului:

- în limbaj natural;

- schemă logică;

- pseudocod;

- în limbaj de programare.

3. Codificarea algoritmului într-un limbaj de programare

4. Testarea programului

4.1. Verificarea corectitudinii sintactice

4.2. Verificarea corectitudinii logice

5. Întreținerea programului

Algoritmul reprezintă o succesiune finită de pasi care, executați într-o ordine bine stabilită,

conduc de la un set de date numite date de intrare la un alt set de date numite date de iesire.

Algoritm

Operaţii de bază

citirea (operaţie

de intrare)

scrierea (operaţie

de ieşire)

atribuirea

Structuri de

control

secvenţa

decizia

iteraţia

Tehnici avansate de programare 2014-2015

Curs 1

3

Pseudocod Limbaj C / C++

Citire CITESTE x (xÎZ) scanf(”%i”,&x);/ cin>>x;

Scriere SCRIE x (xÎZ) printf(”%i”,x);/ cout<<x;

Atribuire var ← expr var = expr;

Secvenţa

instr1

instr2

{

instr1;

instr2;

}

Decizia

DACĂ cond ATUNCI

secv1

ALTFEL secv2

if (cond) secv1;

else secv2;

Iteraţia cu test

iniţial

CÂT TIMP cond EXECUTA

secventa

while (cond)

secventa;

Iteraţia cu test

final

EXECUTĂ

secventa

CÂT TIMP condiție

do

secventa;

while (cond);

Iteraţia cu

contor

PENTRU i← vi,vf,r EXECUTĂ

secventa

for(i=vi;i<=vf;i=i+r)

secventa;

1.2. Elemente de analiză a complexităţii algoritmilor

Analiza complexității unui algoritm are ca scop determinarea (estimarea) volumului de

resurse de calcul necesare pentru execuția algoritmului.

Există două tipuri de resurse:

- spațiul de memorie necesar pentru memorarea datelor prelucrate de algoritm;

- timpul de execuție al tuturor prelucrărilor specificate în algoritm.

Tehnici avansate de programare 2014-2015

Curs 1

4

Putem vorbi astfel despre complexitatea spațială si complexitatea temporală a unui

algoritm. Un algoritm are o complexitate temporală (respectiv spațială) cu atât mai mare, cu cât

timpul (respectiv spațiul de memorie) necesar algoritmului este mai mare.

Dintre cele două resurse de calcul (spațiu si timp) cea critică este timpul de execuție,

calculat ca fiind numărul de pasi executați de algoritm.

În calculul complexității se ține cont numai de operațiile critice din algoritm. Se

consideră ca fiind critice acele operații care prin natura lor fie sunt foarte consumatoare de timp,

fie sunt efectuate de un număr foarte mare de ori (de exemplu, într-un algoritm de sortare o

operație critică este compararea elementelor, întrucât se execută de foarte multe ori).

Volumul de resurse folosite depinde de:

- datele de intrare (de exemplu timpul de sortare a unui vector diferă dacă vectorul este

deja sortat sau este “aproape sortat” sau este “bine amestecat”);

- dimensiunea datelor de intrare (dimensiunea problemei) - de exemplu timpul de sortare

a unui vector cu 5 elemente este mult mai mic decât în cazul unui vector cu 10000 de elemente.

Tipuri de analiză a complexității

- cazul cel mai favorabil - corespunde acelor instanțe ale problemei pentru care numărul

de operații efectuate este cel mai mic (pentru cel mai „prietenos input”). Această analiză permite

identificarea unei limite inferioare a timpului de execuție. Această analiză este utilă pentru a

identifica algoritmii ineficienți (dacă un algoritm are un cost mare în cel mai favorabil caz, atunci

el nu poate fi considerat o variantă acceptabilă).

- cazul cel mai nefavorabil - corespunde instanțelor pentru care numărul de operații

efectuate este maxim (pentru cel mai „neprietenos input”). Această analiză furnizează o limită

superioară a timpului de execuție (algoritmul nu se va purta niciodata mai rău decât atât).

- cazul mediu (complexitatea la care ne putem astepta în cazul inputurilor aleatoare) - o

analiză utilă, însă destul de dificil de realizat.

Tehnici avansate de programare 2014-2015

Curs 1

5

Complexitate exactă, complexitate aproximativă

Complexitatea exactă a unui algoritm este caracterizată de o funcție (numită funcție de

complexitate)
: →  (unde N este mulțimea numerelor naturale, iar R+ este mulțimea

numerelor reale pozitive), f(n) reprezentând volumul de resurse consumate de algoritm pentru

dimensiunea n a problemei rezolvate.