|
|
|
Complexitatea este un indicator al dependenţei dintre dimensiunea datelor de intrare şi numărul de instrucţiuni execute de un algoritm.
|
|
Trebuie să ne alegem un sistem convenabil pentru calculul complexităţii.
Desigur că nu putem să cronometrăm cât de mult ar rula un program pe un anumit calculator, deoarece acest timp nu ar fi caracteristic algoritmului: pe un calculator cu un procesor mai rapid sau mai lent, timpul său de execuţie s-ar modifica.
De fapt, nu putem să ne bazăm nici măcar pe o medie aritmetică statistică a duratei timpului de rulare, deoarece în acest caz am evalua rapiditatea programului, şi eventual a procesoarelor disponibile pe piaţă, ori scopul nostru este de a evalua algoritmul în sine.
De aceea, va trebui să realizăm o evaluare pur teoretică a algoritmului, care să măsoare numărul de instrucţiuni care se execută pentru a ajunge la soluţia problemei.
Totuşi, instrucţiunile variază în cantitate şi în tipul lor.
Pentru a rezolva problema referitoare la tipul instrucţiunilor, s-a presupus că o operaţie de bază se realizează într-o unitate de timp. Toate celelalte instrucţiuni sau serii de instrucţiuni se raportează la această unitate de bază de timp.
De exemplu, citirea unui număr de la tastatură, compararea unei valori cu zero sau afişarea unui caracter pe display se consideră operaţii de complexitate 1. Citirea a n numere de la tastatură va dura n unităţi de timp.
Totuşi, deseori, algoritmii execută un număr diferit de instrucţiuni, în funcţie de datele de intrare. De aceea, nu folosim mereu constanta 1 sau multipli ai acesteia când arătăm complexitatea algoritmului, ci ne folosim de litere care arată dimensiunea datelor de intrare. De exemplu, pentru citirea unei matrici cu m linii şi n coloane, suntem de acord să spunem că se execută n*m operaţii de bază.
Deoarece am notat cu 1 operaţia elementară, am aproximat o constantă cu o unitate. Această constantă diferă de la un procesor la altul, de la o implementare la alta, şi ea nu este relevantă pentru determinarea complexităţii algoritmului, în ansamblu său. De aceea, s-a convenit ca 3*n să fie considerat de aceeaşi complexitate ca n, eliminându-se în general constantele din expresia complexităţii algoritmice.
|
|
Uneori trebuie să comparăm diferite complexităţi pentru a decide care dintre ele este mai bună.
De exemplu, x*x sau x! - care din cei doi algoritmi este mai performant?
Pentru x=1, primul algoritm rulează în 1 instrucţiuni, iar al doilea tot în 1 instrucţiuni.
Pentru x=2, primul algoritm rulează în 4 instrucţiuni, iar al doilea în 2 instrucţiuni.
Pentru x=3, primul - 9 instrucţiuni, al doilea - 6 instrucţiuni.
Pentru x=4, obţinem 16 respectiv 24 de instrucţiuni.
Pentru x=5, obţinem 25 respectiv 120 de instrucţiuni.
Iată că deşi pentru x = 2 şi x = 3 al doilea algoritm se dovedeşte mai performant, începând cu x = 4 complexitatea algoritmului al doilea începe să crească foarte mult, ceea ce îl face practic inutilizabil, mai ales pentru x > 20.
De aceea, când comparăm algoritmii, ne interesează comportarea lor asimptotică, adică ce se întâmplă cu timpul de execuţie când n tinde la infinit. Se observă astfel în exemplul nostru că primul algoritm este mult mai performant decât al doilea.
|
|
Dacă în calculul complexităţii unui algoritm nici un parametru care arată dimensiunea datelor de intrare nu se găseşte la exponent, spunem că avem de a face cu o complexitate polinomială. Mai mult, dacă toţi exponenţii sunt egali cu 1, putem spune că avem de a face cu o complexitate liniară.
În schimb, dacă parametrii apar la exponent, putem spune că avem de a face cu o complexitate exponenţială, deoarece numărul de instrucţiuni pe care algoritmul îl execută creşte exponenţial la o creştere liniară a datelor de intrare.
Din această cauză avem de-a face cu o complexitate exponenţială şi în cazul factorialului, chiar dacă nici un parametru nu apare în formula complexităţii ca exponent.
O clasă importantă de probleme, N-P complete, au complexitate exponenţială.
|
|
Există trei cazuri în care complexitatea unui algoritm se poate măsura. Deşi deseori, cele trei complexităţi sunt egale, există algoritmi în care aceste complexităţi sunt radical diferite.
De exemplu, pentru sortarea unui şir de n numere, există algoritmi care în cazul cel mai favorabil (numerele sunt deja sortate) rulează în n instrucţiuni, în cazul cel mai defavorabil în n*n instrucţiuni, iar în cazul mediu n*ln n instrucţiuni.
Este important să ştim comportarea în aceste cazuri pentru a analiza pe ansamblu comportamentul algoritmului.
|
|