Notiuni de complexitatea algoritmilor

Notiuni de complexitatea algoritmilor

In procesul de rezolvare a problemelor folosind calculatorul se disting urmatoarele faze:

elaborarea algoritmului;

descrierea algoritmului;

demonstrarea corectitudinii algoritmului;

analiza complexitatii algoritmului;

implementarea algoritmului.

Faza de elaborare a algoritmului consta in: crearea unui algoritm pentru rezolvarea problemei propuse. Actul de creare a unui algoritm este un mecanism complex care produce noul printr-o sinteza intre tehnicile fundamentale de elaborare a algoritmilor si creativitatea umana. Aceasta faza este necesara in urmatoarele doua cazuri :

nu se cunosc algoritmi pentru rezolvarea problemei propuse;

algoritmii cunoscuti pentru problema propusa sunt ineficienti.

Faza de descriere a algoritmului consta in exprimarea in mod natural a metodei de rezolvare a problemei dupa care se elaboreaza programul sub forma de schema logica sau in limbaj algoritmic al algoritmului ce urmeaza aceasta metoda.

Faza de demonstrare a corectitudinii algoritmului consta in validarea lui pentru a ne asigura ca algoritmul este corect, independent de limbajul in care el va fi apoi programat.

Faza de analiza a complexitatii algoritmului consta in determinarea unui criteriu de apreciere a algoritmilor pentru a putea decide care dintre algoritmii care rezolva aceeasi problema este mai bun.

Faza de implementare a algoritmului consta din doua subfaze :

programarea algoritmului intr-un limbaj de programare;

testarea programului elaborat.

Aceste faze nu sunt distincte in general si rareori se pot parcurge liniar.

In acest paragraf se va nota cu r cel mai mic intreg, mai mare sau egal cu r, pentru r I R .

Fie un digraf G = (N, A) cu |N| = n noduri si |A| = m arce. Se considera functia valoare b : A R si functia capacitate c : A R. Functia valoare b reprezinta fie functia distanta, fie functia cost, etc. Fie = max si = max .

Definitia 2.10

Prin problema se intelege o functie total definita P : I -> F, unde I este multimea informatiilor initiale (datele de intrare ale problemei) si F este multimea informatiilor finale (datele de iesire ale problemei).

Se presupune ca multimile I si F sunt nevide si cel mult numarabile.

Exemplul 2.10

In reteaua G = (N, A, b) se poate formula problema drumului cel mai scurt, iar in reteaua G = (N, A, c) problema fluxului maxim.

Definitia 2.11

Se numeste instanta a problemei P, precizarea problemei P(i) pentru o valoare specificata i I I .

Pentru o instanta P(i) se va folosi si notatia p, iar prin abuz de notatie, uneori vom scrie p I P.

Exemplul 2.11

In problema drumului cel mai scurt in reteaua G = (N, A, b), pentru a defini o instanta a acestei probleme este necesar sa specificam topologia digrafului G = (N, A), nodurile sursa si destinatie si functia b.

Definitia 2.12

Se spune ca algoritmul a rezolva problema P, daca algoritmul determina solutia oricarei instante p I P.

Un algoritm a care rezolva instanta p va porni de la o codificare a informatiei initiale i I I si va furniza o codificare a rezultatului.

Definitia 2.13

Se numeste dimensiunea problemei P un numar natural, notat d(p), p I P, care reprezinta lungimea unei codificari binare a informatiei initiale.

In general, d(p) este un numar natural care reprezinta dimensiunea structurala a informatiei initiale, deoarece lungimea unei codificari binare a informatiei initiale va fi marginita de o functie avand ca argument dimensiunea sa structurala.

Exemplul 2.12

Sa consideram o problema care are ca data de intrare un digraf G = (N, A) reprezentat prin matricea sa de adiacenta M. Pentru aceasta problema trebuie log n biti pentru codul numarului n si n² biti pentru reprezentarea matricei. Dimensiunea problemei este log n + n². Pentru n suficient de mare, se poate considera dimensiunea problemei egala cu n² .

Exemplul 2.13

Sa consideram o problema care are ca data de intrare o retea G = (N, A, b). Presupunem ca pentru reprezentarea grafului G = (N, A), se folosesc listele de adiacenta P (lista de pointeri) si V (lista nodurilor). Daca notam cu ρ⁺(i) semigradul exterior al nodului i I N, atunci lista P este un tablou unidimensional ce are n+1 elemente cu P(1) = 1 si P(i+1) = P(i) + ρ⁺(i), i = 1, 2, ., n. Lista V este un tablou unidimensional ce are m elemente si V(P(i)) pana la V(P(i+1) - 1) contin succesorii nodului i. Deci 1 P(i) m+1, i = 1, ., n+1 si 1 V(i) n, i = 1, ., m. Deci pentru a descrie aceasta problema sunt necesari :

log n biti pentru codificarea lui n;

log m biti pentru codificarea lui m;

(n+1) log(m+1) biti pentru codificarea elementelor tabloului P;

m log n biti pentru codificarea elementelor tabloului V;

m log b biti pentru codificarea valorilor numerice b(x,y), (x,y)IA.

Rezulta ca dimensiunea problemei este log n log m + (n+1) log(m+1) + m log n + m log b . Pentru m si n suficienti de mari se poate considera ca problema are dimensiunea m log n

In continuare, se vor prezenta diferite abordari ale complexitatii unui algoritm.

Resursele de calcul asociate executiei unui algoritm sunt spatiul de memorie si timpul necesar de executie. Ne vom ocupa numai de resursa timp, deoarece progresele tehnologice din ultima perioada conduc la o scadere a importantei memoriei folosite de algoritm.

Vom nota cu T _a (p) timpul de executie necesar algoritmului a pentru rezolvarea instantei p, pIP. Acest timp reprezinta numarul pasilor efectuati de algoritm pentru rezolvarea instantei p. Un pas al unui algoritm a, este o operatie elementara (instructiune elementara). In general, operatiile elementare sunt: operatii de atribuire, operatii aritmetice (+, -, *, /), operatii logice (comparatii). Se presupune ca executia unei instructiuni elementare nu depinde de marimea operanzilor si de timpul de memorare a rezultatelor. Aceasta inseamna ca resursa timp este studiata independent de sistemul de calcul pe care se face implementarea algoritmului.

In literatura de specialitate, exista trei tipuri de abordari ale complexitatii unui algoritm a : analiza empirica, analiza cazului mediu si analiza cazului cel mai defavorabil.

Obiectivul analizei empirice consta in studierea comportarii in practica a unui algoritm. Se scrie un program pentru algoritmul respectiv si se testeaza performantele programului pe diferite clase de instante ale problemei. Aceasta analiza are cateva dezavantaje majore: (1) performantele unui program depind de limbajul de programare, de calculatorul folosit si de priceperea programatorului care a scris programul; (2) de obicei, aceasta analiza este mare consumatoare de timp si este scumpa; (3) compararea algoritmilor prin aceasta analiza poate sa conduca la rezultate eronate.

Obiectivul analizei cazului mediu consta in studierea comportarii in medie a unui algoritm, care presupune rezolvarea urmatoarelor doua etape: (a) precizarea unei distributii de probabilitate pe multimea instantelor p, pIP; (b) determinarea mediei variabilei aleatoare T _a (p), T^m_a (k) = M( ). Analiza cazului mediu are de asemenea, dezavantaje majore: (1) in general, este dificil sa se determine o distributie de probabilitate corecta pe multimea instantelor p, pIP; (2) aceasta analiza depinde de distributia de probabilitate aleasa; (3) in general, determinarea mediei T^m_a(k) se reduce la calculul unor sume finite care sunt evaluate cu mari dificultati. Totusi aceasta analiza este folosita in cazul cand algoritmul are performante bune pentru majoritatea instantelor si pentru un numar mic de instante, care apar rar in practica, algoritmul functioneaza prost sau foarte prost.

Analiza cazului cel mai defavorabil elimina multe din dezavantajele precizate mai sus. Aceasta analiza consta in a determina T_a (k) = sup. Rezulta ca analiza cazului cel mai defavorabil: (1) furnizeaza o margine superioara pentru numarul operatiilor elementare (instructiunilor elementare) necesare algoritmului a pentru rezolvarea oricarei instante p, pIP ; (2) este independenta de calculatorul pe care se face implementarea algoritmului; (3) face posibila compararea algoritmilor; (4) are si avantajul ca T_a(k) se determina mai usor decat T^m_a(k). Totusi, analiza cazului cel mai defavorabil nu este perfecta. Un dezavantaj major este faptul ca T_a(k) poate fi determinata de instante  patologice  care apar destul de rar in practica. Dar avantajele acestei analize depasesc dezavantajele si de aceea este cea mai folosita metoda pentru a masura performantele unui algoritm.

Deoarece determinarea exacta a lui T_a(k) este uneori dificila, iar pe de alta parte, aceasta ar insemna considerarea unor detalii de implementare, se vor cauta margini superioare si inferioare pentru T_a(k), se va studia comportarea sa asimptotica.

In cele ce urmeaza se vor introduce notatiile Ο, Ω, Θ si se vor defini algoritmii polinomiali si cei exponentiali.

Fie functia f : N N. Se folosesc urmatoarele notatii :

Ο(f) =  ;

Ω(f) =  ;

Θ(f) = .

Se obisnuieste ca in loc de a scrie g I Ο(f) sa se foloseasca notatia g = Ο(f) (similar pentru Ω si Θ).

Definitia 2.14

Se numeste complexitatea timp (sau simplu complexitate) a algoritmului a comportarea asimptotica a lui T_a(k).

Definitia 2.15

Se spune ca o problema algoritmica P are complexitatea O(f(k)) daca exista un algoritm a care rezolva problema P si algoritmul a are complexitatea T_a(k) = O(f(k)).

Definitia 2.16

Se spune ca o problema algoritmica P are complexitatea Ω(f(k)) daca orice algoritm α care rezolva problema P are complexitatea T_α(k) = Ω(f(k)).

Definitia 2.17

Se spune ca un algoritm α pentru rezolvarea problemei P este optimal daca problema P are complexitatea Ω(T_α(k)).

Demonstrarea optimalitatii unui algoritm α pentru o problema P este o activitate foarte complicata. Exista foarte putine rezultate de acest fel.

Definitia 2.18

Se numeste algoritm polinomial un algoritm α cu complexitatea O(f(k)), unde f(k) este un polinom in k. Un algoritm care nu este polinomial se numeste exponential.

Exemplul 2.14

Presupunem ca o operatie elementara necesita pentru executie 10^-6 secunde, adica O(1) = 10^-6 secunde. In tabelul de mai jos sunt prezentate complexitatile timp pentru cateva functii, unde m inseamna minute, z inseamna zile, iar s inseamna secole.

Exemplul 2.15

Sa consideram graful G = (N, A) reprezentat prin matricea sa de adiacenta M. Unele probleme de teorie a grafurilor necesita calcularea matricei M^n-1, unde prin Mⁱ notam, in acest exemplu, puterea booleana de ordinul i a matricei M. Deci problema P consta in calculul matricei M^n-1.

Dintr-un exemplu prezentat mai sus, rezulta ca dimensiunea problemei este n².

Daca avem de efectuat produsul boolean a doua matrice booleene (cu elemente 0,1) B si C patratice, de dimensiune n, atunci pentru calculul matricei produs D = BC trebuie determinate toate elementele d_ij = b_i1c₁₁b_inc_nj, unde , reprezinta inmultirea booleana, respectiv adunarea booleana. Convenim sa consideram ca operatie elementara perechea ordonata (,). Rezulta ca, pentru calculul unui element d_ij sunt necesare n operatii elementare. Deci, pentru calculul a n² elemente d_ij sunt necesare n³ operatii elementare. Fie

n-1 = log(n-1)

In acest caz avem . Acest produs boolean contine cel mult k inmultiri booleene, deoarece daca a_i = 0, atunci (matricea unitate) si nu se mai efectueaza inmultirea. Consideram cazul cel mai defavorabil cu a_i = 1, i = 0, . , k, k = log(n-1) - 1. Algoritmul necesita atunci:

Calculul matricelor booleene:

M, M² = MM, . ,

ce reprezinta k inmultiri booleene de matrice booleene;

Calculul matricelor booleene:

M³ = MM², M⁷ = M³ M⁴, M¹⁵ = M⁷ M⁸, .

ce reprezinta k inmultiri booleene de matrice booleene.

Deci pentru a calcula M^n-1 trebuie sa efectuam in cazul cel mai defavorabil, 2k inmultiri booleene de matrice booleene. Cum pentru inmultirea booleana a doua matrice booleene sunt necesare n³ operatii elementare, rezulta ca pentru calculul matricei M^n-1 sunt necesare 2n³k operatii elementare. Deoarece k = log(n-1) - 1 si dimensiunea problemei este n², rezulta ca algoritmul pentru calculul matricei M^n-1 are complexitatea O(n^3/2log n).

In continuare se vor prezenta anumite reguli de calcul pentru O, Ω, . Mai intai sa precizam ca relatiile O, Ω, pot fi considerate ca relatii intre functii: O este relatia "este dominata asimptotic de", Ω este relatia "domina asimptotic pe", si este relatia "are acelasi ordin de marime ca". Se constata usor ca relatiile O si Ω sunt relatii de pre-ordine (reflexiva si tranzitiva) si ca relatia este o relatie de echivalenta (reflexiva, simetrica si tranzitiva).

Regulile de calcul pentru O, Ω, sunt urmatoarele:

Reflexivitatea relatiilor O, Ω,

a.    f = O(f)

b.    f = Ω(f)

c.    f = (f)

Simetria relatiei

g = (f) implica f = (g)

Tranzitivitatea relatiilor O,

a.    g = O(f) si f = O(h) implica g = O(h)

b.    g = Ω(f) si f = Ω(h) implica g = Ω(h)

c.    g = (f) si f = (h) implica g = (h)

Fie c R^*₊ :

a.    g = O(f) implica cg = O(f)

b.    g = Ω(f) implica cg = Ω(f)

c.    g = (f) implica cg = (f)

Fie g₁ g₂ sau g₁ g₂ :

a.    g₁ = O(f₁) si g₂ = O(f₂) implica g₁+g₂ = O(max(f₁,f₂))

b.    g₁ = Ω(f₁) si g₂ = Ω(f₂) implica g₁+g₂ = Ω(min(f₁,f₂))

c.    g₁ = (f₁) si g₂ = (f₂) implica g₁+g₂ = (max(f₁,f₂))

Fie g₁ g₂ :

a.    g₁ = O(f₁) si g = O(f₂) implica g₁-g₂ = O(f₁)

b.    g Ω(f ) si g₂ f₂) implica g₁-g₂ = Ω(f₂)

c.    g (f ) si g f₂) si f = Ω(f ), f = O(f ) implica g g (f

Fie g₁g sau g₁g

a.    g₁ = O(f₁) si g = O(f₂) implica g₁∙g = O(f₁∙f

b.    g₁ (f₁) si g (f₂) implica g₁∙g (f ∙f

c.    g₁ (f₁) si g (f₂) implica g₁∙g (f₁∙f

Aceste reguli sunt consecinte evidente ale definitiilor.

Deseori, se pot compara functiile f si g, calculand

Se obtin urmatoarele proprietati:

Aceste proprietati rezulta din definitia limitei: de exemplu, pentru proprietatea de la punctul 1) avem: e > 0, n₀ IN astfel incat n 0 avem sau e > 0, n₀ IN astfel incat n n₀ avem:

(c-є) f(n) < g(n) < (c+є) f(n)

Reciprocele proprietatilor 1), 2), 3), sunt false. In cazul cand nu exista limita, trebuie revenit la definitiile lui O, Ω, , pentru a putea compara g si f. De exemplu, daca f(n) = 2n, g(n) = n, pentru n = 2k+1 si g(n) = 2n, pentru n = 2k, atunci limita de mai sus nu exista, dar g I (f), deoarece pentru orice n avem f(n) g(n) f(n).