Exemplu:Problema turnurilor din Hanoi c1j19ji
Se dau n discuri: a1, a2, ... , an de dimensiuni diferite, cu d1 < d2 < ... < dn , di - fiind diametrul discului. Discurile respective sunt stivuite pe o tija:

Se cere sa se deplaseze aceasta stiva pe o alta tija, folosind ca manevra o tija auxiliara, respectƒndu-se conditia << Un disc nu poate fi plasat decƒt peste un disc mai mare >>.
Problema P(n) a deplasarii a n discuri, se rezolva prin deplasari succesive ale discurilor de pe o tija pe alta. Deplasarea de pe o tija pe alta este echivalenta cu deplasarea a n-1 discuri de pe tija intiala
(ti) pe tija de manevra, apoi plasarea celui mai lung disc pe tija finala, pentru ca la sfƒrsit sa se aduca de pe tija de manevra (tm), pe tija finala
(tf), cele n-1 discuri deplasate.
Primele miscari s-ar figura astfel:

Procedura Hanoi:

Hanoi(n, ti, tf, tm)
A if(n=1) then muta (ti, tf) //deplaseaza discul superior // de pe ti pe tf else | Hanoi(n-1, ti, tm, tf)
| muta(ti, tf)
|_ Hanoi(n-1, tm, tf, ti)
S
Pentru o problema P(1) , timpul T(1) = 1 , pentru o mutare.
Pentru P(n) , timpul:
(1)
Dorim sa aflam ordinul de complexitate a lui T(n).
Asociem relatiei (1) ecuatia caracteristica:

Facƒnd identificarea:
Ordinul este O(2n), adica o complexitate exponentiala.
Relatii de recurenta. Clasele relatiilor de recurenta
1.f(n) = aùf(n - 1) + b x0 = aùx0 + b
Prin scaderea celor doua relatii, rezulta un algoritm exponential cu baza a: f(n) - x0 = a (f(n-1) - x0)
2.f(n)=aùf(n-1)+bùf(n-2) f(n) = tü => tü = aùt(la n-1) + bùt(la n-2)
Facƒnd n = 2, tý = aùt + b , cu urmatoarele cazuri: a) t1 , t2 apartin R => solutia ecuatiei este de forma: f(n)=alfaùt1ü+betaùt2ü iar alfa si beta se calculeaza din conditiile initiale: cu x1 si x2 constante.
Astfel, este rezolvata ecuatia recursiva. b) t1 = t2 = t Solutia este de forma: c) t1, t2 C Solutia este de forma:
In care si C, = (conjugat) solutia trigonometrica:

3.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 Œmparte vectorul
Œn 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)
A if(low high) return else | |½ low + high ½|
| mid=| ---------------- | //partea Œntreaga
| |_ 2 _|
| MERGE_SORT(A, low, mid) //sortare separata
| MERGE_SORT(A, mid+1, high) //sortare separata
|_MERGE(A, low, mid, high) //interclasare
S

Procedura MERGE interclaseaza secventele sortate Aalowömidi si Aamid+1öhighi.
Pentru aceasta este nevoie de un vector auxiliar B, de aceeasi dimensiune cu A.

MERGE(A, low, mid, high)
A i=low; j=mid+1; k=low;
while i mid and j high do
|½ if Aaii <A aji then Baki=Aaii; i=i+1
| else Baki = Aaji; j=j+1
|_ k = k+1
while i mid do
|½ Baki = Aaii; i=i+1
|_ k = k+1
whilej high do
|½ Baki = Aaji; j=j+1
|_ k = k+1 for k=low to high do
Aaki = Baki;
S

Aratam complexitatea procedurii MERGE_SORT: O(nlog n)
Aceasta functie cere pentru o secventa cn operatii.
Timpul de executie al algoritmului este:

Consideram: n = 2k;
T(n) = 2T(n/2) + n = 2(2T(n/4) + n/2) + n = ... = 22úT(n/22) + 2n=
22 (2úT(n/23) + n/22) + 2n =
= 23T(n/23) + 3n = ... = 2kT(n/2k) + kn T(n) = kn = nlog2n , pentru ca n = 2k , si, deci, k = log2n.

Asadar complexitatea algoritmului este O(nlog 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 lg(n) operatii.
Se demonstreaza, analog, si relatia de recurenta:

Solutia acestei ecuatii de recurenta este:

Utilizƒnd aceste retete putem calcula complexitatile pentru: algoritmul Merge_Sort: a = 2 , b = 2 , k = 1 , bk = a complexitatea O(nklog n) algoritmul Binary_Search: a = 1 , b = 2 , k = 0 complexitatea
O(n0log n) = O(log n), (situatia ak= b).

4.Relatii de recurenta cu istorie completa
Exemplu:

Exemplu: Algoritmul Quick_Sort

Quik_Sort(A, low, high)
A if(high low) then
|½ k= Partition(A, low, high) // procedura de |
// partitionare |
| Quick_Sort (A, low, k-1)
|_ Quick_Sort(A, k+1, high)
S

Pseudocodul pentru functia partition:

Partition(A, low, high)
A l= low; h= high; x= Aali;
while (l <h) do
I |½ while (Aali x) and (l _high)
| do l= l+1
II | while (Aali >x) and (h low)
| do h= h-1
|_ if (l <h) then interchange (Aali, Aahi) interchange (Aahi, Aalowi) return(h);
S

Algoritmul considera pivotul ca fiind: Aalowi. Indicele l parcurge vectorul de la stƒnga la dreapta, iar indicele h parcurge vectorul de la dreapta la stƒnga. Ei se apropie pƒna se Œntƒlnesc (l = h). Deci, l lasa Œn urma numai elemente Aaii pivot, iar h lasa Œn urma numai elemente Aaii pivot.

Ciclul I while Œnseamna ca Œnainteaza l cƒt timp Aali pivot. Acest ciclu se opreste pe conditia
Aahi pivot, fixƒndu-se aici.
Ciclul II while Œnsemna ca Œnainteaza h cƒt timp Aahi pivot. Acest ciclu se opreste pe conditia
Aahi pivot, fixƒndu-se aici.

Cele doua pozitii se schimba, astfel Œncƒt sa se permita Œnaintarea indicilor mai departe.

Pentru aflarea complexitatii, cercetam cazul cel mai defavorabil. Fie cazul
Œn care vectorul este ordonat descrescator. Pivotul gasit, la primul pas, este elementul maxim din vector, rezulta ca trebuie plasat Œn ultima pozitie.

Pivotul va fi maximul dintre elementele secventei, deci, va fi plasat Œn ultima pozitie din secventa.
Problema se Œmparte Œn 2 subprobleme: P(n) P(n-1) , P(0).
Numarul de comparatii pentru functia Partition este (n-1). Vectorul se parcurge
Œn doua directii, dar o singura data.
Rezulta ca timpul de functionare al algoritmului Quick_Sort este:
Rezolvƒnd aceasta ecuatie, avem:

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

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

Studiul complexitatii algoritmului Quick_Sort Œn caz mediu
Pentru complexitatea medie trebuie considerata probabilitatea tuturor aparitiilor datelor de intrare. Consideram ca orice configuratie de date la intrare este egal probabila. Probabilitatea ca pivotul sa fie plasat Œn pozitia k este egala pentru . Asadar, pivotul va fi plasat Œn pozitia k prin partitionare, cu o probabilitate egala cu 1/n, pentru .

Suma tuturor probabilitatilor este 1. Evenimentul este plasarea pivotului Œn pozitia k. Consideram Ti(n) timpul de executie al algoritmului Quick_Sort atunci cƒnd pivotul este plasat Œn pozitia i:

Rezulta:
Timpul mediu va fi o medie aritmetica:
Dezvoltƒnd,

(Facƒnd schimbarea de variabila j = n - i + 1)
Rezulta relatia de recurenta cu istorie completa:

Aceasta se rezolva astfel: Œnmultind relatia cu n rezulta:
Scriem acum relatia Œnlocuind pe n cu n+1:
Si scazƒndu-le acum membru cu membru rezulta: care se Œnmulteste cu: ,
Notam:
Facƒnd o majorare:

(un element nu se ordoneaza).
Rezulta: si este aria zonei de sub graficul functiei .

unde O(nln n) este complexitatea acestei functii.

Analiza spatiului de memorie consumat Œntr-un algoritm
Algoritmi recursivi
Algoritmii recursivi consuma memorie suplimentara pentru simularea recursivitatii.
Fie urmatoarea procedura recursiva:

parcurgere(l) // l - lista Œnlantuita (pointer la primul element)
A if(l 0)
|½ parcurgere(link(l))
|_ prelucrare(data(l)) // exemplu: afisare
S
Functia afiseaza o lista invers, de la coada la cap.

Apelul functiei se face astfel: se creeaza Œn stiva programului o "Œnregistrare de activare" Œn care sunt memorate:
- parametrii de apel;
- adresa instructiunii de retur (cu care va continua programul dupa terminarea executiei functiei); se rezerva spatiu pentru variabile locale. se executa instructiunile functiei care folosesc pentru parametri si variabile locale din "Œnregistrarea de activare"; se scoate din stiva "Œnregistrarea de activare" (decrementarea vƒrfului stivei), stiva fiind ordonata; se continua cu instructiunea data de adresa de retur memorata Œn
"Œnregistrarea de activare".

Asadar, variabilele globale (statice) sunt memorate Œntr-o zona de memorie fixa, mai exact Œn segmentele de date. Variabilele automate (locale) se memoreaza Œn stiva, iar variabilele dinamice Œn "heap"-uri (cu malloc Œn C, si cu new Œn C++).

Consumul de memorie al algoritmului recursiv este proportional cu numarul de apeluri recursive ce se fac. Variabilele recursive consuma mai multa memorie decƒt cele iterative. La prelucrarea unei liste, daca primul element nu este vid, se prelucreaza acesta, urmƒnd apoi ca restul listei sa fie considerata ca o noua lista mai mica, etc.

De exemplu, algoritmul Quick_Sort:

Quick_Sort(A, low, high)
A if(low < high)
|½ k = Partition(A, low, high)
| Quick_Sort(A, low, k-1)
|_Quick_Sort(A, k+1, high)
S

Avem Œn acest algoritm doua apeluri recursive.
Cazul cel mai defavorabil:

Consideram consumul de memorie Œn stiva : M(n) = c + M (n - 1) M(n) = O(n) un ordin de complexitate mare.
Pentru reducerea consumului de memorie, se concepe un alt algoritm la

Quick_Sort, astfel Œncƒt un apel sa fie rezolvat recursiv, iar celalalt apel iterativ.

Quick_Sort(A, low, high)
A
while (low < high)
|½ k = Partition(A, low, high)
| if( k-low > high-k)
| |½ Quick_Sort(A, k+1, high)
| |_high = k-1
| else
| |½ Quick_Sort(A, low, k-1)
| _|_low = k-1
S

Necesarul de memorie pentru aceasta este M(n) c + M(n/2), Œnsemnƒnd ca oricare ar fi secventa mai mica, ea este decƒt jumatatea M(n) = O(log n) am redus ordinul de complexitate.

Liste generalizate
Definitie:
Data o multime de elemente (atomi), se numeste lista generalizata o secventa finita (1, 2, ... , n), Œn care i sunt atomi.

Exemplu: A = (a, b, c)
B = (x, A, (a, c), ( ))
| | | \ atom lista lista lista vida

Observatie: Listele generalizate pot sa aiba elemente comune. Se permite definirea de liste recursive.
Reprezentarea listelor generalizate
Presupunem o lista de forma: (tag, data, link) Œn care tag este o eticheta
A0,1S.
Daca tag = 0 nodul va corespunde unui element atomic cƒmpul data va contine atomul respectiv.
Daca tag = 1 nodul va corespunde unei subliste cƒmpul data va semnifica legatura la primul element al sublistei; link este legatura pentru urmatorul nod din lista.
Fie urmatoarele primitive de selectie pentru un nod de adresa p: p adresa unui nod; link(p) cƒmpul "link" din nodul indicat de p;
Notam: tag(p) cƒmpul "tag" din nodul indicat de p data(p) cƒmpul "data" din nodul indicat de p
Fie urmatoarele liste:
D = ( )
A = (a, (b, c))
B = (A, A, ( ))
C = (a, C) cu urmatoarele reprezentari:
D : o lista vida Œnseamna un pointer nul

Ne propunem sa dam nume unei subliste, deci daca tag = 1, adica tag(p) = 1 data(p) va fi adresa unei structuri ce contine:

Asadar, obtinem urmatoarea reprezentare:

Operatii la liste generalizate: functia insert, este asemanatoare cu cea de la liste Œnlantuite. Elementul ce se insereaza poate fi un atom sau o sublista; functia del ( ) trebuie sa tina seama de existenta unor liste comune. Deci, este necesara pastrarea Œn elementul ce contine numele listei A si a unui indicator care sa contorizeze numarul de referinte ale lui.

Exemplu:

Numai daca acest indicator este 0, se face stergerea efectiva a listei.

Traversarea listelor generalizate
Traversarea listelor generalizate presupune prelucrarea elementelor listei, si a elementelor sublistelor componente.

Exemplu: O functie de copiere si o functie de test de egalitate a doua liste generalizate, realizate recursiv si iterativ. Functia returneaza o copie a listei. Copie mai Œntƒi primul element, si apoi recursiv restul listei:

Varianta recursiva:

Copy (l) // l - lista Œnlantuita
A if (l = 0) then return (0) else |½ p = get_sp()
| data(p) = data(l)
| link(p) = Copy(link(l))
|_ return(p)
S
Copy (l) // l - lista generalizata
A if (l = 0) then return (0) else |½ p = get_sp()
| if (tag(l) = 0) then data(p) = data(l)
| else data(p) = Copy(data(l))
| link(p) = Copy(link(l))
|_ return(p)
S

Functia pentru testarea egalitatii este:

isEqual (l1,l2) // procedura tratata iterativ
A p1 = l1; p2 = l2
while(p1 0 and p2 0)
|½ if (data(p1) data(p2)) then return (FALSE)
| p1 = link(p1)
|_ p2 = link(p2) return(p1 = p2)
S isEqual (l1,l2) // procedura tratata recursiv
A p1 = l1; p2 = l2
while(p1 0 and p2 0)
|½ if (tag(p1) tag(p2)) then return (FALSE)
| if (tag(p1) = 0 and data(p1) data(p2)) then return (FALSE)
| if (tag(p1) = 1 and not isEqual(data(p1),data(p2)) then return (FALSE)
| p1 = link(p1)
|_ p2 = link(p2) return (p1 == p2)
S