Complexitatea algoritmilor (Lectia 1)

Complexitatea algoritmilor (Lectia 1)***********************************************Anunt:Am observat aici pe forum ca sunt persoane care ar dori sa afle ceva despre modalitatea de estimare a timpului de executiei a unui program sau a cantitatii de memoriei folosite de program. As dori intii sa-mi cer scuze pentru o romana stilcita dar o sa incerc sa ma exprim cit mai clar si succint posibil.Daca o sa fiti interesati (prin discutii active) in continuarea lectiilor atunci am sa mai scriu daca nu atunci lectia curenta va fi prima si ultima.***********************************************Deci cum masuram timpul de executie a unui program (algoritm)? Iata ceva exemple de programe simple:Exemplu 1:i:=0;Exemplu 2:j:=0;for i:=1 to n,j:=j+i;endExemplu 3:k:=0;for i:=1 to n,for j:=1 to n,k:=k+i+j;endendSa incepem cu Exemplu 1. Care e timpul de executiei al acestui program, minute, ore, zile, etc? Pai depinde ce arhitectura avem la dispozitie x86, PowerPC sau de frecventa de tact al procesorului.Sa consider ca timpul de executie al programului 1 e T_1=c. Adica timpul T_1 de executie e o constanta "c" a carei valoare nu este relevanta la momentul de fata.Trecem la Exemplu 2. Timpul de executie a instructiunei j:=0 o consideram iarasi find egala cu o constanta "c" care depinde de configuratia procesorului. Pentru a simplifica lucrurile luam iarasi "c" ca timp de executie pentru instructiunea j:=j+i. Deci care este timpul total de executie T_2 al programului 2? Pai sumam timpul de executie a fiecarei instructiuni sau mai bine zis T_2=c+n*c. Atrageti atentie ca termenul "n*c" e legat de faptul ca instructiune j:=j+1 va fi executata de "n"-ori.In sfirsit trecem la Exemplu 3. Aici iarasi consideram un timp constant "c" de executie pentru instructiunile k:=0 si k:=k+i+j. Acum timpul total T_3 de executie al programului 3 va fi T_3=c+n*c+...+n*c=c+n*n*c. Nu e greu de vazut ca instructiunea k:=k+i+j va fi executata de "n*n"-ori. Ca rezultat obtinem urmatoarele:T_1=cT_2=c+n*cT_3=c+n*n*cAici exista o singura problema si ea consta in valoarea constantei "c". Asa cum si am mai scris "c" depinde de configuratia procesorului adica la diferite sisteme timpul de executie va fi diferit. Dar in acelas moment noi suntem interasati sa stim cit de efectiv e algoritmul nostru la orice sistem neluind in consideratie structura lui (viteza procesorului, etc).Iata aici noi trebuie sa definim notiunea de complexitatea in timp al unui algoritm. Complexitatea in timp al unui algoritm arata legatura intre intrararea unui sistem (in cazul nostru e "n") si numaral de pasi efectuati de algoritm.Deci idea de baza consta in masurarea numarului de pasi si nu timp (sec, min, etc) efectuati de algoritm cind la intrare se da o valoare "n". Si cum masuram noi complexitatea in timp al unui algoritm? Intii consideram ca la intrare se da un numar mare "n". E evident ca pentru valori mici ale lui "n" nu prea are sens sa masori eficienta algoritmului. Cel mai important e sa vezi eficienta algoritmului cind "n" e foarte mare. Apoi consideram urmatoare notatie O sau altfel notatia Landau:Pentru doua functii f(n) si g(n) avem urmatoare relatie:f(n)=O(g(n)) cind n->infinit, daca si numai daca, pentru orice numar M si n' avem relatia |f(n)|n'.Ca sa nu ne afundam in matematica intuitia e ca orice functie f(n) poate fi marginita (bounded) de o alta functie g(n) sau f(n)=O(g(n)) daca se indeplineste conditia de mai sus.f(n)=O(g(n)) - inseamna ca functia f(n) e marginita de g(n).Si acum care e scopul acestei notatii O? Pai scopul e de a obtine asa un g(n) din un f(n) astfel incit g(n) contine o expresie care depinde numai de "n" si nu de orice alta constanta "c". Deci ca rezultat obtinem complexitatea algoritmului in pasi si mai mult ca atit aceasta complexitate depinde de valoare "n" data la intrare.Rescriem T_1, T_2 si T_3 de mai sus ca niste functii ce depind de n sau:T_1(n)=cT_2(n)=c+n*cT_3(n)=c+n*n*cFunctiile T_1(n), T_2(n) si T_3(n) reprezinta funtia f(n). Acum cum calculam functia g(n) pentru fiecare T_1(n), T_2(n) sau T_3(n)? Pai iata asa o simpla regula, toate constantele "c" ce apar in fata variabilei "n" se transforma in 1, daca exista o suma dintr-o variabila "n" la orice putere si o constanta "c" atunci "c" va fi egala cu zero, sau mai bine zis pentru exemplele 1,2 si 3 avem urmatoarele complexitati in timp:T_1(n)=O(1)T_2(n)=O(n)T_3(n)=O(n*n)Iata pentru cei interesati asa un exercitiu:k:=0;for i:=1 to n,for j:=1 to n-i+1,k:=k+i+j;endendAdica sa se calculeze complexitatea in timp folosind notatia O.P.S. Va rog toate discutiile sa fie la tema. Multumesc.