Ne propunem să lămurim modul în care se estimează timpul de calcul necesar unui program pentru a furniza rezultatul.
Să considerăm, una din cele mai simple probleme. Se dă un vector cu n componente. Se cere sa se calculeze maximul dintre componentele sale.
Reamintim, pe scurt algoritmul:
Timpul de calcul depinde, în primul rînd, de lungimea(mărimea) datelor de intrare, pe care o vom nota cu n.
Exemple:
Pentru a calcula timpul de calcul ar trebui inventariem toate instrucţiunile programului şi să ştim d cîte ori se execută fiecare din ele(în funcţie de n).Mai mult, ar trebuie să cunoaştem cît durează execuţia fiecărui tip de instrucţiune.
Observaţie 1.
Exemplu. Pentru calculul maximului, nu putem şti de cîte ori se execută atribuirea max:=v[i]. Cu toate acestea putem considera că există o proporţionalitate între valoarea n şi numărul de execuţii.
Observaţia 2.
Datorită acestor considerate vom proceda astfel.
Se alege o operaţie numită operaţie de bază, şi se vede de cîte ori se execută aceasta. Cerinţa pentru operaţia de bază este ca aceasta să se execute de un număr de ori, numărul care să poată calcula de la început pornind de la n.
Exemplu.
În astfel de cazuri(cînd avem de ales între mai multe operaţii de bază), vom alege acea operaţie care corespunde cît mai bine scopului propus.
Astfel, dacă analizăm un algoritm de generare a permutării comparativ cu altele de aceeaşi natură vom alege ca operaţie de bază comparaţia.
În cazul în care analizăm un algoritm oarecare, în care soluţia este sub formă de permutare, putem considera ca operaţie de bază permutarea. Problema se spune în felul următor: dacă căutăm soluţia printre toate permutările pe care se pot genera vom avea n! căutări(un număr imens !), oare nu se poate altfel?
Exemple de probleme la care se foloseşte un astfel de raţionament: problema comis voiajorului, problema celor n dame.
Timpul estimat de calcul se trece sub formă aproximativă astfel:
O(număr estimat de execuţii ale operaţiei de bază)
Exemplu de exprimare a timpului.
Dacă un algoritm efectuiază 3n2+7n+5 operaţii de bază, vom spune că aceasta este un algoritm cu O(n2).
Exemple.
În cazul de faţă operaţia aleasă este cea de comparare. Pentru un vector cu n componente se fac n-1 comparaţii. Aceasta înseamnă că dacă vectorul are o sută de componente se fac 99 de comparaţii ş.a.m..d.. Se poate demonstra faptul că un algoritm mai bun nu există!
2. Pentru generarea permuntărilor(în cazul în care se consideră ca operaţie de bază generarea unei permutări) timpul estimat de calcul este O(n!).
În anumite cazuri nu putem preciza nici macar numărul de execuţie ale operaţiilor de bază.
Exemplu. Sortarea prin interschimbare(vezi 6.2.1). În cazul în care vectorul este sortat se execută n-1 comparaţii (se parcurge vectorul o singură dată), dacă vectorul este sortat invers se execută n(n-1)/2 operaţii de bază (se parcurge vectorul de n ori).
În astfel de cazuri se poate considera:
De fiecare dată cînd se trece timpul estimat se precizează despre care este vorba (minim, mediu, maxim). În practică, prezintă interes timpul madiu sau maxim.
Dacă timpul estimat este sub forma O(nk), k=N*, spunem că algoritmul este în timp polinomial.
Exemlu. Sortarea prin interschimbare are timpul (mediu, maxim) polinomial şi anume O(n2).
Un algoritm în O(n) se numeşte algoritm liniar.
Dacă un algoritm are un timp estimat O(2n), O(3n).. spunem că algoritmul este în timp exponenţial.
Un algoritm în timp O(n!) este asimilat unui algoritm în timp exponenţial.
n!=1x2x…n<2x2x….x2=2n-1.
În practică nu sunt admişi decît algoritm în timp polinomial, deşi nu este deloc indiferent gradul polinomului.
Şi totuşi pentru ce tot acest efort de estimare a timplui de calcul? Oare viteza de lucru a unui calculator nu este atît de mare, în cît abstracţie făcînd de cîteva minute de calcul, în plus sau în minus, să renunţăm la estimarea lui? Răspunsul la această la această întrebarea este categoric negativ. Mai mult timpul de calcul este esenţial dacă este prea mare algoritmul nu are nici un fel de valoare practică. Să ne imaginăm un algoritm care are un timp de calcul O(2n). Dacă n este de 10, calculatorul va efectua aproximativ 1024 operaţii elementare. Dacă n este 100 acesta va trebui să efectueze 1024*1024*…*1024 operaţii elementare, adică un număr mai mare decît 1000*1000*…*1000 adică 1000000…0000 (de treizeci de ori). Aceasta este un număr imens. Dar dacă n este 1000? pentru un n nu foarte mare, nici cel mai modern calculator din lume nu scoate rezultatul decît în sute sau în mii de ani. De astfel ce înseamnă în asemenea cazuri un calculator modern? Să presupunem că un sistem PENTIUM are o viteză de circa 25 de ori mai mare decît un sistem XT. Să presupunem că avem un program care are un timp de calcul de ordinul O(2n). Se cere să rezolvăm o problemă pentru n=30. Fie că timpul necesar rulării acestei probleme pe un XT. Această problemă va fi rulată pe PENTIUM în timpul t/25. Dorim să rezolvăm problema pe PENTRIUM pentru n=35 (n a crescut numai cu 5). Dar 235=230*25=32*230. Deci dacă n a crescut cu 5, vom avea nevoie de mai mult timp de lucru să rezolvăm problema pe PENTIUM decît timpul pentru rezolvarea ei pentru n=30 pe XT.
Vă daţi seama ce înseamnă un timp de calcul de ordinul O(2n)? Sporul lui n cu o singură unitate duce la dublarea timpului de calcul.
Ce concluzie tragem de aici? De cîte ori avem de rezovat o problemă căutăm pentru aceasta un algoritm în timp polinomial (polinomul va avea gradul minim). Mai mult căutăm un algoritm care să rezovle problema în timp polinomial de grad minim.
