Cozi inlantuite

Cozi inlantuite

O coada poate fi implementata printr‑o lista inlantuita la care operatiile de acces sunt restrictionate corespunzator.

Este nevoie de doi indicatori (pointeri):

head indica primul element din coada (primul care va fi scos);

tail indica ultimul element din coada (ultimul introdus).

O coada vida va avea: head=tail=nil

In mod obisnuit, adaugarea unui element in coada modifica numai tail iar stergerea unui element numai head. Intr‑un mod special trebuie sa fie tra 828c29i tate cazurile:

adaugare intr‑o coada vida:

Initial: head=tail=nil

Final: Coada cu un element:

stergere dintr‑o coada cu un element:

Initial: Coada cu un element

Final: head=tail=nil

In aceste cazuri se modifica atat head cat si tail.

Facem notatiile :

C.head pointer la primul element din coada;

C.tail pointer la ultimul element din coada;

C coada.

Conditia de coada vida este head=0.

Operatiile cozii inlantuite

Functia put insereaza un element in coada, in pozitia fata:

put(C,a)

Functia get scoate un element din pozitia fata:

get(C,a)

Functia front returneaza elementul din fata cozii, fara a-l scoate din coada.

front(C)

isEmpty(C)

Exista aici un element de redundanta: ar fi convenabil sa nu mai avem spatiu suplimentar de memorare, ci, sa avem un singur pointer ca sa putem manevra coada. De aceea apar utile cozile inlantuite circulare.

Cozi inlantuite circulare

Daca reprezentam coada printr‑o structura inlantuita circulara va fi nevoie de un singur pointer prin intermediul caruia se pot face ambele operatii de adaugare si stergere din coada:

Fie:

C pointer la primul () element din coada

link(C)    pointer la ultimul() element din coada

Operatiile de plasare si de scoatere din coada, sunt:

put(C,a)

get(C)

front(C)    returneaza data(link(C))

isEmpty(C)    retuneaza conditia C=0.

Complexitatea algoritmilor

La evaluarea (estimarea) algoritmilor se pune in evidenta necesarul de timp si de spatiu de memorare al lui.

Studierea complexitatii presupune analiza completa in cadrul algoritmului a urmatoarelor 3 puncte de vedere:

configuratia de date cea mai defavorabila (cazurile degenerate);

configuratia de date cea mai favorabila;

comportarea medie.

Punctul 3 presupune probabilitatea de aparitie a diferitelor configuratii de date la intrare.

Punctul 1 este cel mai studiat si este folosit, de obicei, pentru compararea algoritmului. Si in ceea ce priveste timpul, se studiaza configuratia cea mai defavorabila a algoritmului.

Complexitatea unui algoritm se noteaza cu: O(f(n)).

Definitie

Fie f : N N si g : N N doua functii.

Spunem ca f I O(g) si notam f = O(g) daca si numai daca o constanta c I R si un numar n I N astfel incat pentru n > n f(n) < c g(n)

Observatie:

f : N N este o functie f(n) cu n dimensiunea datelor de intrare.

f(n) reprezinta timpul de lucru al algoritmului exprimat in 'pasi'.

Lema 1

Daca f este o functie polinomiala de grad k, de forma:

f(n) = a_k n^k + a_k-1 n^k-1 + + a₁ n + a₀, atunci f = O(n^k).

Facandu-se majorari in membrul drept, obtinem rezultatul de mai sus:

f(n) = a_k n^k a_k-1 n^k-1 a n + a < n^k a_k a_k-1 a ) < n^k c pentru n > 1 T f(n) < c n^k, cu n

Concluzie: f = O(n^k , si ordinul O exprima viteza de variatie a functiei, functie de argument.

Exemplu: Calcularea maximului unui sir

maxsir(A,n)

Exprimam:

T(n) timpul de executie in pasi al acestui algoritm;

T(n)= 1 + 2(n-1) = numarul de atribuiri si comparatii

Cazul cel mai defavorabil: situatia in care vectorul este ordonat crescator (pentru ca de fiecare data se face si comparatie si atribuire).

Putem spune ca T(n) = O(n), este o functie polinomiala de gradul I. Conteaza doar Ordinul polinomului, nu coeficientul termenului de grad maxim. Iar la numararea pasilor ne concentram asupra numarului buclelor, nu asupra pasilor din interiorul buclei.

Exemplu: Insertion Sort (algoritmul de sortare prin inserare)

Algoritmul INSERTION SORT considera ca in pasul k, elementele A[1÷k‑1] sunt sortate, iar elementul k va fi inserat, astfel incat, dupa aceasta inserare, primele elemente A[ ÷k] sa fie sortate.

Pentru a realiza inserarea elementului k in secventa A[1÷k‑1], aceasta presupune:

memorarea elementului intr‑o varibila temporara;

deplasarea tuturor elementelor din vectorul A[1÷k‑1] care sunt mai mari decat A[k], cu o pozitie la stanga (aceasta presupune o parcurgere de la dreapta la stanga);

plasarea lui A[k] in locul ultimului element deplasat.

Complexitate: O(n)

insertion_sort(A,n)

Cazul cel mai defavorabil: situatia in care deplasarea (la dreapta cu o pozitie in vederea inserarii) se face pana la inceputul vectorului, adica sirul este ordonat descrescator.

Exprimarea timpului de lucru:

T(n) = 3·(n - 1) + (1 + 2 + 3+ + n - 1) = 3(n-1) + 3n (n - 1)/2

Rezulta complexitatea: T(n) = O(n functie polinomiala de gradul II.

Observatie: Cand avem mai multe bucle imbricate, termenii buclei celei mai interioare dau gradul polinomului egal cu gradul algoritmului.

Bucla cea mai interioara ne da complexitatea algoritmului.

Exemplu: Inmultirea a doua matrici

prod_mat(A,B,C,n)

Rezulta complexitatea O(n

Exemplu: Cautarea binara(Binary Search)

Fie A, de ordin n, un vector ordonat crescator. Se cere sa se determine daca o valoare b se afla printre elementele vectorului. Limita inferioara se numeste low, limita superioara se numeste high, iar mijlocul virtual al vectorului, mid (de la middle).

Binary_search(A,n,b)

Calculul complexitatii algoritmului consta in determinarea numarului de ori pentru care se executa bucla while.

Se observa ca, la fiecare trecere, dimensiunea zonei cautate se injumatateste. Cazul cel mai defavorabil este ca elementul cautat sa nu se gaseasca in vector. Pentru simplitate se considera n = 2^k unde k este numarul de injumatatiri.

Rezulta k = log₂ n si facand o majorare, T(n) log n + 1 n, a.i. 2^k n < 2^k+1

Rezulta complexitatea acestui algoritm: este O(log n). Dar, baza logaritmului se poate ignora, deoarece: log_ax = log_bx * log_ab si log_ab este o constanta, deci ramane O(log n), adica o functie logaritmica.

Proprietati:

1) Fie f, g : N N

Daca f = O(g) T | k f = O(g)

| f = O(k g) , k I R constant.

2) Fie f, g, h : N N.

si: f = O(g) |

g = O(h) | T f = O(h)

3) Fie f , f , g , g : N N

si: f = O(g T | f₁ + f = O(g + g

f = O(g | T | f f = O(g g

Aceasta proprietate permite ca, atunci cand avem doua bucle imbricate (de complexitati diferite), complexitatea totala sa se obtina inmultindu-se cele doua complexitati. Cele doua complexitati se aduna, daca buclele sunt succesive.

Teorema

Oricare ar fi doua constante c > 0, a > 1, si f : N N, o functie monoton strict crescatoare, atunci:

(f(n))^c= O(a^f(n)

Demonstratia se bazeaza pe limita:

Intre clasa functiilor logaritmice, si cea a functiilor polinomiale exista relatia: O(n^c O(aⁿ

Au loc urmatoarele incluziuni:

O(1) O(log n) O(n) O(n log n) O(n O(n^k log n) O(n^k+1 O(2ⁿ

Pentru calculul complexitatii se va incerca incadrarea in clasa cea mai mica de complexitate din acest sir:

O(1) clasa algoritmilor constanti;

O(log n) clasa algoritmilor logaritmici;

O(n) clasa algoritmilor liniari;

O(n log n) clasa algoritmilor polilogaritmici;

O(n clasa algoritmilor patratici;

O(n^k log n) clasa algoritmilor polilogaritmici;

O(n^k+1 clasa algoritmilor polinomiali;

O(2ⁿ clasa algoritmilor exponentiali.

Tehnici de calcul a complexitatii

Se folosesc urmatoarele sume:

Sa calculam, de exemplu, suma:

Se noteaza:   

Prin aceeasi tehnica se calculeaza suma: