Un algoritm este o metoda pentru rezolvarea unei clase de probleme cu calculatorul.
Complexitatea unui algoritm consta in cost. Acest cost este calculat in functie de mai multe criterii
care pot face diferenta dintre un program eficient si unul mai putin eficient. Dintre cele mai uzuale
criterii de evaluare a calitatii unui program putem aminti timpul de executie, marimea programului,
memoria ocupata la rulare sau algoritmii folositi pentru rezolvarea cerintelor programului. Aceste
criterii depind de scopul pentru care a fost creat programul, din al carui punct de vedere criteriile
pot sa fie mai mult sau mai putin importante.
Acest curs analizeaza metodele (algoritmii) utilizate pentru rezolvarea problemelor si calculul
,,costului" asociat acestor metode, vazut in general ca timp de executie.
Rularea unui program ,,dureaza" un anumit timp. In functie de algoritmul utilizat, rezolvarea
unei probleme poate ,,dura" mai mult sau mai putin timp. Pentru unele probleme, a caror rezolvare
necesita mai mult timp de executie, se pot descoperi metode mai rapide. Cantitatea de resurse (timp,
memorie etc.) necesara executiei unui anumit tip de program este analizata de complexitatea
calcului.
Ne asteptam ca timpul de executie al unui program sa depinda de cantitatea de date de intrare.
Intr-un fel sunt procesate cateva sute de date de intrare si in alt fel sunt procesate cateva milioane de
date de intrare. Durata atasata complexitatii calcului este proportionala cu informatia trimisa
programului pentru a fi procesata. (Este mai usor sa sortam 10 numere decat sa sortam 1000 de
numere).
De exemplu, ganditi-va la urmatoarea situatie: ,,Tocmai am scris un program pentru obtinerea
matricei inverse a unei matrice de intrare, de marime nxn, cu timp de executie de 1,2n3 minute".
Aici observam o descriere tipica a problemei complexitatii calcului. Timpul de rulare este
proportional cu marimea matricei de intrare.
Un program mai rapid poate rula de exemplu in 0,8n3 minute pentru o matrice nx n Daca
cineva ar face o descoperire importanta am putea sa descrestem exponentul. Un timp de 7n2,8
minute ar putea reprezenta, de exemplu, o imbunatatire excelenta.
O procesare garantata pentru cel mult cn3 pentru o intrare de marime n este considerata ca
,,usoara". Una care necesita n10 este tot usoara. Daca pentru o matrice nx n sunt necesare in schimb
2n minute atunci avem o problema grea. Cateodata, pentru procesari considerate usoare, avem un
timp foarte lung, dar inca acceptabil, din punctul de vedere al cerintelor, atata timp cat se poate
exprima printr-o functie polinomiala avand ca parametru de intrarea cantitatea de date prelucrata de
algoritm.
In general, daca timpul de procesare se poate exprima printr-o functie polinomiala de n , unde
n reprezinta numarul de date introduse spre procesare in program, putem considera ca procesarea
este ,,usoara", altfel este considerata ,,grea".
Multe dintre problemele stiintei calculatoarelor sunt considerate ca fiind usoare. Pentru a
convinge pe cineva ca o problema este usoara este suficient sa-i descrii o metoda rapida de
rezolvare a problemei respective. Este mai dificil sa convingi pe cineva ca o problema este grea,
adica sa dovedesti ca este imposibil sa gasesti o cale usoara de rezolvare.
In stiinta calculatoarelor nu este suficient sa gasesti un anumit algoritm si sa te lamentezi ca
este incet. Acel algoritm poate fi incet, dar poate ca exista si o cale mai eficienta de rezolvare a
problemei (un algoritm mai rapid).
Inversarea matricelor este usoara deoarece exista o metoda (metoda eliminarii Gaussiene) care
poate inversa o matrice nx n intr-un timp de cel mult cn3
Pentru a da un exemplu de problema grea trebuie sa deviem un pic de la subiectul nostru.
Problema aleasa este cea a ,,aranjarii figurilor" - ,,tiling problem"1. Sa presupunem ca primim un
1 Martin Gardner, Articol, Scientific American, Ianuarie 1977, pp. 110-121
ANALIZA ALGORITMILOR SI COMPLEXITATEA CALCULULUI
3
numar infinit de figuri in forma de hexagon regulat. Putem sa acoperim o suprafata fara sa lasam
spatii libere si fara sa suprapunem figurile. Putem sa facem acest lucru si daca figurile sunt
dreptunghiuri identice. Daca sunt pentagoane nu mai putem acoperi suprafata. In Figura 1 este
exemplificata umplerea unei suprafete cu figuri dreptunghiulare identice, iar in Figura 2 este
exemplificata umplerea cu figuri hexagonale.
Figur
Documentul este oferit gratuit,
trebuie doar să te autentifici in contul tău.
