Algoritmii recursivi sunt un concept fundamental în știința calculatoarelor. Ei rezolvă problemele prin descompunerea lor în subprobleme mai mici, similare. Înțelegerea complexității lor temporale ajută la evaluarea eficienței și performanței lor.

Ce este complexitatea timpului?

Complexitatea timpului măsoară modul în care timpul de funcționare al unui algoritm crește cu dimensiunea de intrare. Se exprimă folosind notația Big O, care descrie limita superioară a ratei de creștere a algoritmului.

Analiza Algoritmilor Recursive

Algoritmii recursivi implică adesea rezolvarea unei probleme prin apelarea la aceeași funcție cu intrări mai mici. Pentru a analiza complexitatea lor de timp, este esențial să înțelegem relația de recurență, care exprimă timpul total bazat pe subprobleme mai mici.

Metode comune de calcul

Pentru rezolvarea relaţiilor recurente sunt utilizate două metode primare:

  • Metoda substituţiei: Ghiciţi soluţia şi verificaţi-o prin inducţie.
  • Metoda de respingere a arborelui: Vizualizează recidiva ca pe un copac pentru a rezuma costurile la fiecare nivel.

De exemplu, recurența T(n) = 2T(n/2) + n descrie un algoritm de divizare și cucerire. Rezolvarea acestui fapt produce o complexitate temporală a O(n log n).