Informatică Algoritmi
Formule pentru calculul complexitatii temporale a algoritmilor
Complexitatea temporală a unui algoritm estimează timpul de execuție în funcție de dimensiunea datelor de intrare, notată cu O (notația Big O). Aceasta descrie comportamentul asimptotic, ignorând constantele și termenii de ordin inferior. De exemplu, un algoritm cu buclă simplă peste n elemente are complexitatea O(n).
Formule de bază
- O(1) - timp constant Operații care durează același timp indiferent de intrare, cum ar fi accesul la un element dintr-un vector prin index.
- O(n) - timp liniar Algoritmi care parcurg datele o singură dată, cum ar fi căutarea secvențială într-un vector: for(i=0; i<n; i++).
- O(n²) - timp pătratic Algoritmi cu bucle imbricate, cum ar fi bubble sort: for(i=0; i<n; i++) for(j=0; j<n-i-1; j++).
- O(log n) - timp logaritmic Algoritmi care reduc problema la jumătate la fiecare pas, cum ar fi căutarea binară într-un vector sortat.
Exemple de calcul
- 1 Identifică operația dominantă Numără de câte ori se execută cea mai costisitoare operație, cum ar fi comparațiile în sortări.
- 2 Aplică regulile Big O Ignoră constantele (de exemplu, 2n devine O(n)) și păstrează cel mai mare termen (n² + n devine O(n²)).
- 3 Verifică cu date concrete Pentru n=1000, O(n) înseamnă aproximativ 1000 operații, O(n²) înseamnă 1.000.000 de operații.
Exersează analiza pe algoritmi simpli pentru a înțelege cum cresc timpii cu dimensiunea datelor.