Limbajul Python 3 - Complexitatea algoritmilor

PYTHON 3

PAG. 1 / 1

Complexitatea algoritmilor

Introducere

Studiul complexitǎţii algoritmilor a apǎrut din necesitatea oamenilor de a gǎsi o modalitate prin care sǎ rezolve anumite probleme rapid. Deşi calculatoarele cu cele mai noi tehnologii pot executa într-un timp extrem de scurt un set foarte mare de operaţii, anumite probleme, aparent banale, ce conţin multe variabile reale şi cu multe cifre, necesitǎ câteva minute, ore sau chiar ani pentru a fi rezolvate. Deci, "dimensiunea" problemei reprezintǎ un factor important în determinarea complexitǎţii ei.

Exemple: înmulţirea repetatǎ a unor matrice cu un numǎr foarte mare de elemente, diverse tehnici de prelucrare a imaginilor, ș.a.m.d.

Exprimarea complexității

Fiind dat un anumit algoritm, se pune problema să găsim un indicator care să exprime complexitatea sa. Acest indicator va face abstracție de calculatorul pe care rulează programul obținut în urma cuantificării algoritmului într-un limbaj de programare, precum și de limbajul de programare ales. Altfel spus, indicatorul va exprima complexitatea unui algoritm care poate fi redactat în pseudocod, schemă logică sau limbaj de programare.

Presupunem că algoritmul are n date de intrare și acestea urmează să fie prelucrate. Indicatorul care exprimă complexitatea va ține cont de acest număr.

Exemple:
a) Se cere să se calculeze valoarea maximă a unui șir de n numere reale;
b) Să se determine dacă n numere reale sunt distincte. Se va compara primul număr cu toate celelalte, al doilea cu cele care îi urmează, etc.

Un algoritm conține mai multe operații de atribuire, decizionale, scriere și citire. Acestea se execută de un număr de ori care depinde de n, dar și de datele propriu-zise. Teoretic, ar trebui să se determine de câte ori se execută fiecare operație. Cum această cerință este imposibil de realizat în practică, s-a preferat o altă metodă. Mai precis, se alege o operație de bază, se determină de câte ori se execută aceasta și se presupune că restul operațiilor se execută de un număr de ori care este proporțional cu numărul de executări a operației de bază. De regulă, operația de bază aleasă este operația decizională (if).

Exemple:
a) Pentru a calcula valoarea maximă a unui șir de n numere reale se efectuează n-1 comparații.
b) Pentru a determina, prin algoritmul de mai sus dacă n numere reale sunt distincte, se efectuează:

comparații.

Exprimarea complexității unui algoritm se face aproximativ. în cazul în care expresia care cuantifică numărul de operații de bază este sub formă de polinom, ca în exemplele date, se precizează numai primul termen al acestuia, fără coeficient. Pentru a preciza că este vorba de o cuantificare aproximativă, vom nota complexitatea prin O(f(n)).

Exemple:
a) Algoritmul care calculează maximul a n numere reale are complexitatea O(n), deși se efectuează doar n-1 comparații.
b) Algoritmul care decide dacă n numere reale sunt distincte are complexitatea O(n²), deși se efectuează cel mult n(n-1)/2 comparații.

Algoritmii de complexitate O(n) se mai numesc și algoritmi liniari.

Algoritmii de complexitate O(n^k) se mai numesc și algoritmi polinomiali.

Complexitate exponențială

Bineînțeles, există algoritmi care au complexitate exponențială, adică de forma O(aⁿ).

Exemplu: se cere să se afișeze toate submulțimile mulțimii {1,2,...,n}. Avem 2ⁿ submulțimi ale unei mulțimi de numere reale. Dacă considerăm ca operație principală afișarea unei submulțimi, înseamnă că algoritmul are complexitatea O(2ⁿ).

În practică trebuie evitați algoritmii care nu au complexitate polinomială. Imaginați-vă că pentru un n dat, un calculator performant rulează programul într-o oră. Dacă mărim pe n cu 10, avem 2ⁿ⁺¹⁰ operații elementare, adică 1024 × 2ⁿ operații. Prin urmare, programul va rula pe același calculator 1024 de ore. Dar dacă mărim pe n cu 1000? Practic, pentru valori nu prea mari ale lui n, algoritmii exponențiali sunt de neutilizat.

Există și algoritmi care sunt asimilați celor exponențiali, precum cei factoriali.

Exemplu: se cere să se afișeze toate permutările mulțimii {1,2,...n}. Avem n! permutări. Dacă considerăm ca operație de bază afișarea unei permutări, avem n! operații elementare, deci algoritmul are complexitatea O(n!). Dar n!=1×2×3×...×n > 1×2×2×...×x2=2^n-1.

Complexitate logaritmică

Există și algoritmi care au complexități de forma O(log(n)), O(n×log(n)), O(n²×log(n)), unde prin log(n) înțelegem log₂(n). Rețineți:

Cu alte cuvinte, prin logaritm în baza 2 din x (log₂(x)) înțelegem puterea la care trebuie ridicat numărul 2 astfel încât 2ⁿ=x.

Exemplu: log₂(1024) = 10 < 1024.

Nedeterminist Polinomial

În anii 1960 deja apǎruserǎ anumite probleme, aparent simple, care nu se puteau rezolva în timp polinomial. Astfel, s-a decis ca, pentru a afirma cǎ o problemǎ se poate rezolva în timp polinomial, o soluţie corectǎ trebuie sǎ poatǎ fi verificatǎ în timp polinomial de algoritmul propus.

Acest procedeu se numeşte certificarea soluţiei şi a impus apariţia unei noi clase, NP. O clasǎ de probleme pentru care se pot verifica rǎspunsurile corecte în timp polinomial se numeşte NP (Nedeterminist Polinomial).

O problemǎ este NP-dificilǎ dacǎ un algoritm pentru rezolvarea sa poate rezolva oricare altǎ problemǎ din clasa NP. Cu alte cuvinte, orice problemǎ NP se reduce polinomial la ea.

Anumite probleme NP sunt extrem de dificile şi S. Cook a demonstrat cǎ dacǎ una dintre ele se poate rezolva în timp polinomial, atunci toate problemele NP pot fi rezolvate în timp polinomial (1971). Acestǎ afirmaţie poartǎ denumirea de "Teorema lui Cook", iar clasa acestor probleme se numeşte NP-completǎ. Acest rezultat a fost descoperit şi publicat (1973), independent, de cǎtre Leonid Levin în U.R.S.S.

O problemǎ este NP-completǎ dacǎ orice problemǎ NP-dificilǎ se reduce polinomial la ea.

Existǎ o serie de probleme NP-complete pentru care încǎ nu au fost descoperite soluţii...

Bibliografie

1. "Tehnici de Optimizare - Aplicații", autori: Călin SOARE, Vlad TUDOR, ISBN: 978-973-7658-09-8, Editura L&S Infomat, București.
2. "Bioinformatica", autor: Victor MITRANA, ISBN: 978-973-7658-22-7, Editura L&S Infomat, București.
3. "Manual de Informatică pentru clasa a IX-a, profilul real intensiv (varianta C++)", autor: Tudor Sorin, ISBN: 978-973-7658-30-2, Editura L&S Infomat, București.