Analiza spatiului de memorie consumat intr-un algoritm

Analiza spatiului de memorie consumat intr-un algoritm

Algoritmi recursivi

Algoritmii recursivi consuma memorie suplimentara pentru simularea recursivitatii.

Fie urmatoarea procedura recursiva:

parcurgere(l) // l - lista inlantuita (pointer la primul //element)

Functia afiseaza o lista invers, de la coada la cap.

Apelul functiei se face astfel:

se creeaza in stiva programului o 'inregistrare de activare' in 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 'inregistrarea de activare';

se scoate din stiva 'inregistrarea de activare' (decrementarea varfului stivei), stiva fiind ordonata;

se continua cu instructiunea data de adresa de retur memorata in 'inregistrarea de activare'.

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

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

De exemplu, algoritmul Quick_Sort:

Quick_Sort(A, low, high)

Avem in acest algoritm doua apeluri recursive.

Cazul cel mai defavorabil:

Consideram consumul de memorie in stiva : M(n) = c + M (n - 1) T M(n) = O(n) T un ordin de complexitate mare.

Pentru reducerea consumului de memorie, se concepe un alt algoritm la Quick_Sort, astfel incat un apel sa fie rezolvat recursiv, iar celalalt apel iterativ.

Quick_Sort(A, low, high)

Necesarul de memorie pentru aceasta este M(n) c + M(n/2), insemnand ca oricare ar fi secventa mai mica, ea este decat jumatatea T M(n) = O(log n) T am redus ordinul de complexitate.

Liste generalizate

Definitie:

Data o multime de elemente (atomi), se numeste lista generalizata o secventa finita (a a a_n), in care a_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) in care tag este o eticheta I

Daca tag = 0 T nodul va corespunde unui element atomic T campul data va contine atomul respectiv.

Daca tag = 1 T nodul va corespunde unei subliste T campul 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) campul 'link' din nodul indicat de p;

Notam:    tag(p) campul 'tag' din nodul indicat de p

data(p) campul '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 inseamna un pointer nul

Ne propunem sa dam nume unei subliste, deci daca tag = 1, adica tag(p) = 1 T 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 inlantuite. 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 in 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 intai primul element, si apoi recursiv restul listei:

Varianta recursiva:

Copy (l)    // l - lista inlantuita

Copy (l)    // l - lista generalizata

Functia pentru testarea egalitatii este:

isEqual (l ,l // procedura tratata iterativ

isEqual (l₁,l₂)    // procedura tratata recursiv