Relatii de recurenta. Clasele relatiilor de recurenta

Relatii de recurenta. Clasele relatiilor de recurenta

f(n) = a f(n - 1) + b

x = a x + b

Prin scaderea celor doua relatii, rezulta un algoritm exponential cu baza a: f(n) - x = a (f(n-1) - x

f(n) = tⁿ T tⁿ = a t^n-1 + b t^n-2

Facand n = 2, T t = a t + b , cu urmatoarele cazuri:

a) t₁ , t₂ I R T solutia ecuatiei este de form 555g61f a: iar a si b se calculeaza din conditiile initiale:

cu x_{1 si} x_{2 constante.}

Astfel, este rezolvata ecuatia recursiva.

b) t t t T Solutia este de forma:   

c) t , t I C T Solutia este de forma:   

In care a si b I C, b = (conjugat) T solutia trigonometrica:

Clasa de relatii de recurenta pentru algoritmi de tip 'divide et impera'

Exemplu: Algoritmul Merge Sort (sortare prin interclasare)

Pentru a sorta o secventa de n elemente ale unui vector A, se imparte vectorul in 2 segmente de lungime n/2 pe care le sorteaza separat recursiv, dupa care urmeaza interclasarea.

Pseudocod: Procedura MERGE_SORT primeste ca argumente A ‑ vectorul de sortat, si doi indici care delimiteaza o portiune din acest vector. Apelul initial va fi MERGE_SORT(A, 1, n).

MERGE_SORT(A, low, high)

Procedura MERGE interclaseaza secventele sortate A[low÷mid] si A[mid+1÷high]. Pentru aceasta este nevoie de un vector auxiliar B, de aceeasi dimensiune cu A.

MERGE(A, low, mid, high)

Aratam complexitatea procedurii MERGE_SORT: O(n log n)

Aceasta functie cere pentru o secventa c n operatii.

Timpul de executie al algoritmului este:

Consideram: n = 2^k

T(n) = 2 T(n/2) + n = 2 T(n/4) + n/2) + n = = 2 ·T(n/2 ) + 2n= 2 (2·T(n/2 ) + n/2 ) + 2n =
= 2 T(n/2 ) + 3n = = 2^k T(n/2^k) + k n T T(n) = k n = n log n , pentru ca n = 2^k , si, deci, k = log n.

Asadar complexitatea algoritmului este O(n log n)

Pentru a rezolva problema de dimensiune n, se rezolva pentru a probleme de dimensiune n/b, iar combinarea rezultatelor celor a prbleme, duce la g(n) operatii.

Se demonstreaza, analog, si relatia de recurenta:

Solutia acestei ecuatii de recurenta este:

Utilizand aceste retete putem calcula complexitatile pentru:

algoritmul Merge_Sort: a = 2 , b = 2 , k = 1 , b^k = a T complexitatea O(n^k log n)

algoritmul Binary_Search: a = 1 , b = 2 , k = 0 T complexitatea O(n log n) = O(log n), (situatia a^k= b).

Relatii de recurenta cu istorie completa

Exemplu:   

Exemplu: Algoritmul Quick_Sort

Quik_Sort(A, low, high)

Pseudocodul pentru functia partition:

Partition(A, low, high)

Algoritmul considera pivotul ca fiind: A[low]. Indicele l parcurge vectorul de la stanga la dreapta, iar indicele h parcurge vectorul de la dreapta la stanga. Ei se apropie pana se intalnesc (l = h). Deci, l lasa in urma numai elemente A[i] pivot, iar h lasa in urma numai elemente A[i] > pivot.

Ciclul I while inseamna ca inainteaza l cat timp A[l] pivot. Acest ciclu se opreste pe conditia
A[h] > pivot, fixandu-se aici.

Ciclul II while insemna ca inainteaza h cat timp A[h] > pivot. Acest ciclu se opreste pe conditia
A[h] pivot, fixandu-se aici.

Cele doua pozitii se schimba, astfel incat sa se permita inaintarea indicilor mai departe.

Pentru aflarea complexitatii, cercetam cazul cel mai defavorabil. Fie cazul in care vectorul este ordonat descrescator. Pivotul gasit, la primul pas, este elementul maxim din vector, rezulta ca trebuie plasat in ultima pozitie. Pivotul va fi maximul dintre elementele secventei, deci, va fi plasat in ultima pozitie din secventa.

Problema se imparte in 2 subprobleme: P(n) P(n-1) , P(0).

Numarul de comparatii pentru functia Partition este (n-1). Vectorul se parcurge in doua directii, dar o singura data.

Rezulta ca timpul de functionare al algoritmului Quick_Sort este:

Rezolvand aceasta ecuatie, avem:

unde: T(1) este 0 (nu se partitioneaza). Rezulta:

Aceasta suma este de complexitate O(n . Rezulta ca este un algoritm ineficient.