Algoritmica -Curs 5 1Curs 5: [605335]

Algoritmica -Curs 5 1Curs 5:
Analiza eficienț eialgoritmilor (II)

Algoritmica -Curs 5 2In cursul anterior…
… am v ăzutcare sunt etapele principale ale analizei eficien ței
algoritmilor :
•Identificarea dimensiunii problemei
•Identificarea operaț ieidominante
•Estimarea timpului de execuț ie(determinarea numărului de
execuț ii ale operaț ieidominante)
•Dacătimpul de execuț iedepinde de propriet ățiledatelor de intrare
atunci se analizeaza:
–Celmaifavorabil caz=> margine inferioar ăa timpului de
execuț ie
–Celmaidefavorabil caz=> margine superioar ăa timpului de
execuț ie
–Cazmediu=> timp mediu de execuț ie

Algoritmica -Curs 5 3Azi vom vedea ca…
… scopul principal al analizei eficientei algoritmilor este săse
determine modul în care timpul de execuț ieal algoritmului creșteo
datăcu creșterea dimensiunii problemei
… pentru a obțineaceast ăinformaț ienu este necesar săse
cunoasc ăexpresia detaliat ăa timpului de execuț iecieste
suficient săse identifice :
–Ordinul de creștereal timpului de execuț ie(în raport cu
dimensiunea problemei )
–Clasa de eficien ța (complexitate) căreiaîiaparținealgoritmul

Algoritmica -Curs 5 4Structura
•Ceeste ordinul de creștere ?
•Ceeste analiza asimptotic ă?
•Cateva notaț ii asimptotice
•Analiza eficien țeistructurilor fundamentale de prelucrare
•Clase de eficien ță
•Analiza empiric ăa eficien țeialgoritmilor

Algoritmica -Curs 5 5Ceeste ordinul de creștere?
In expresia timpului de execuț ieexistăde regul ăun termen care
devine semnificativ maimare decât ceilalț itermeni atunci când
dimensiunea problemei crește.
Acest termen este denumit termen dominant șiel dicteaz ă
comportarea algoritmului în cazul în care dimensiunea problemei
devine mare
T1(n)=an+b
T2(n)=a log n+b
T3(n)=a n2+bn+c
T4(n)=an+b n +c
(a>1)Termen dominant: a n
Termen dominant: a log n
Termen dominant: a n2
Termen dominant: an

Algoritmica -Curs 5 6Ceeste ordinul de creștere?
Sa analiz ăm cese întâmplăcu termenul dominant cânddimensiunea
problemei creștede k ori:
T1(n)=an
T2(n)=a log n
T3(n)=a n2
T4(n)=anT’1(kn)= a kn=k T1(n)
T’2(kn)=a log(kn)=T2(n)+alog k
T’3(kn)=a (kn)2=k2T3(n)
T’4(kn)=akn=(an)k=T4(n)k

Algoritmica -Curs 5 7Ceeste ordinul de creștere?
Ordinul de creștereexprim ăcum creștetermenul dominant al
timpului de execuț ieîn raport cu dimensiunea problemei
Ordin de crestere
Liniar
Logaritmic
Patratic
ExponentialT’1(kn)= a kn=k T’1(n)
T’2(kn)=a log(kn)=T’2(n)+alog k
T’3(kn)=a (kn)2=k2T’3(n)
T’4(kn)=akn=(an)k=(T’4(n))k

Algoritmica -Curs 5 8Cum poate fiinterpretat ordinul de cre ștere?
Cândse compar ădoialgoritmi , celavândordinul de creșteremaimic
este considerat a fimaieficient
Obs: comparaț iase realizeaz ăpentru dimensiuni mari ale
dimensiunii problemei (cazul asimptotic )
Exemplu. Consideram următoarele două expresii ale timpului de
execuț ie
T1(n)=10n+10 ( ordin liniar de creștere)
T2(n)=n2(ordin pătratic de creștere)
Daca n<=10 atunci T1(n)>T2(n)
In acest cazordinul de creștereeste relevant doar pentru n>10

Algoritmica -Curs 5 9O comparaț iea ordinelor de creștere
n log2n nlog2n n2 2n n!
10 3.3 33 100 1024 3628800
100 6.6 664 10000 1030 10157
1000 10 9965 1000000 10301102567
10000 13 132877 100000000 1030101035659Diferite tipuri de dependen ță a timpului de execuție în raport cu
dimensiunea problemei

Algoritmica -Curs 5 10O comparaț iea ordinelor de creștere
n log2n nlog2n n2 2n n!
10
10-8sec3.33*10
-9sec333*10
-8sec10010
-7sec102410
-6sec36288000.003 sec
10010
-7sec6.66*10
-9sec6646*10
-7sec1000010
-5sec1030
1013ani10157
10140 ani
1000
10-6sec10
10-8sec99659*10
-6sec10000000.001 sec10
301
10284ani102567
102550 ani
10000
10-5sec13
1.3* 10-8sec13287710
-3sec1000000000.1 sec10
3010
102993 ani1035659
1035642 aniIpoteză: fiecare opera ție este executata in 10-9sec
Obs: pt timpi de execu ție care depind exponențial sau factorial de dimensiunea
problemei prelucrarea devine imposibil de executat daca n :10

Algoritmica -Curs 5 11Compararea ordinelor de cre ștere
Ordinele de creșterea doitimpi de execuț ieT1(n) șiT2(n) pot fi
comparate princalculul limitei raportului T1(n)/T2(n) cand n tinde la
infinit
Daca limita este 0atunci se poate spune ca T1(n) are un ordin de
creșteremaimicdecât T2(n)
Daca limita este o constant ăfinităstrict pozitiv ăc (c>0) atunci se
poate spune căT1(n) șiT2(n) au acelaș iordin de creștere
Daca limita este infinit ăatunci se poate spune ca T1(n) are un
ordin de creșteremaimare decât T2(n)

Algoritmica -Curs 5 12Structura
•Ceeste ordinul de creștere ?
•Ceeste analiza asimptotic ă?
•Cateva notaț ii asimptotice
•Analiza eficien țeistructurilor fundamentale de
prelucrare
•Clase de eficien ță
•Analiza empiric ăa eficien țeialgoritmilor

Algoritmica -Curs 5 13Ceeste analiza asimptotic ă?
•Analiza timpilor de execuț iepentru valori miciale dimensiunii
problemei nu permite diferenț ierea dintre algoritmii eficien țișicei
ineficien ți
•Diferenț eledintre ordinele de creșteredevin din ceîn cemai
semnificative pemăsura cecreștedimensiunea problemei
•Analiza asimptotic ăare ca scop studiul propriet ățilortimpului de
execuț ieatunci cânddimensiunea problemei tinde cătreinfinit
(probleme de dimensiune mare)

Algoritmica -Curs 5 14Ceeste analiza asimptotic ă?
•In funcțiede propriet ățiletimpului de execuț iecânddimensiunea
problemei devine mare, algoritmul poate fiîncadrat in diferite
clase identificate prinniștenotaț ii standard
•Notaț iilestandard utilizate în identificarea diferitelor clase de
eficien țăsunt:
(Theta)
O (O)
Ω(Omega)

Algoritmica -Curs 5 15Fie f,g: N->R+ doua funcții care depind de dimensiunea problemei șiiau
valori pozitive
Defini ție.
f(n) (g(n)) daca exista c1, c2> 0 sin0N astfel incat
c1g(n) ≤f(n) ≤c2g(n) pentru orice n≥n0
Notatie. Frecvent , in locul simbolului de apartenenta se foloseste celde
egalitate:
f(n)= (g(n)) (f(n) are acelasi ordin de creștereca sig(n))
Exemple.
1. T(n) = 3n+3 T(n) (n)
c1=2, c2=4, n0=3, g(n)=n
2. T(n)= n2+10 nlgn +5 T(n) (n2)
c1=1, c2=2, n0=40, g(n)=n2Notaț ia

Algoritmica -Curs 5 16Notaț ia
02040608010005000100001500020000Ilustrare grafic ă. Pentru valori mari ale luin, f(n) estemarginit ă, atât
superior cât șiinferior de g(n) î nmul țit cu nișteconstante pozitive
f(n)= n2+10 nlgn +5c2g(n)=2n2
c1g(n)=n2Nu are importan ță
comportarea pentru
valori mici ale luin
n0c1g(n) ≤ f(n) ≤ c2g(n)
(n2)

Algoritmica -Curs 5 171. DacăT(n)=aknk+ak-1nk-1+…+a1n+a0atunci T(n) (nk)
Dem. Intrucat T(n)>0 pentru orice n rezulta ca ak>0.
Deci T(n)/ nk->ak(cand n->).
Deci pentru orice ε>0 exista N(ε) astfel incat
|T(n)/ nk-ak|< ε=> ak-ε<T(n)/ nk<ak+ εpentru orice n>N( ε)
Sa presupunem ca ak-ε>0.
Considerand c1=(ak-ε), c2=ak+ εsin0=N(ε) se obtine
c1nk< T(n) <c2nkpentru orice n>n0, adica T(n) (nk)Nota ția. Propriet ăți

Algoritmica -Curs 5 182.(c g(n))= (g(n)) pentru orice constanta c
Dem. Fie f(n) (cg(n)).
Atunci c1cg(n) ≤ f(n) ≤ c2cg(n) pentru orice n≥n0.
Considerand c’1= cc1sic’2= c c2se obtine ca f(n) (g(n)).
Astfel rezulta ca (cg(n)) (g(n)).
In mod similar se poate demonstra ca (g(n)) (cg(n)), adica
(cg(n))= (g(n)).
Cazuri particulare:
a) (c)= (1)
b) (logah(n))= (logbh(n)) pentru orice a,b>1
Obs. Baza logaritmilor nu este relevant ă, astfel căse vaconsidera în
majoritatea cazurilor căse lucreaz ăcu baza 2. Notatia. Propriet ăți

Algoritmica -Curs 5 193. f(n)  (f(n)) (reflexivitate)
4. f(n) (g(n)) => g(n)  (f(n)) (simetrie)
5. f(n) (g(n)) , g(n) (h(n)) => f(n) (h(n)) (tranzitivitate)
6. (f(n)+g(n)) = (max{f(n),g(n)}) Notaț ia. Propriet ăți

Algoritmica -Curs 5 203. 3n<=T(n) <=4n -1 T(n) (n)
c1=3, c2=4, n0=1
4. Inmul țireaa doua matrici: T(m,n,p )=4mnp+5mp+4m+2
Extinderea defini ției(în cazul în care dimensiunea problemei depinde de
maimulte valori ):
f(m,n,p ) (g(m,n,p ))dacăexistă
c1, c2>0 sim0,n0 ,p0N astfel încât
c1g(m,n,p ) <=f( m,n,p ) <=c2g(m,n,p ) pentru orice m>=m0, n>=n0, p>=p0
Astfel T(m,n,p ) (mnp)
5. Căutare secvenț ială: 6<= T(n) <= 3(n+1) ( sau4<=T(n)<=2n+2)
Daca T(n)=6 atunci nu se poate găsic1astfel încât 6 >= c1n pentru valori
suficient de mari ale luin. Rezult ăcăT(n) nu aparținelui(n).
Obs: Exista timpi de executie (algoritmi ) care nu aparțin unei clase de tip
Notaț ia. Alteexemple

Algoritmica -Curs 5 21Defini ție.
f(n)O(g(n)) dacăexistăc >0 ș in0N astfel încât
f(n) <=c g(n) pentru orice n>=n0
Notaț ie.f(n)= O(g(n)) (f(n) are un ordin de creșterecelmult egal cu cel
al luig(n))
Exemple.
1. T(n) = 3n+3 T(n) O(n)
c=4, n0=3, g(n)=n
2. 6<= T(n) <= 3(n+1) T(n) O(n)
c=4, n0=3, g(n)=n Notaț iaO

Algoritmica -Curs 5 22Ilustrare grafica. Pentru valori mari ale luin, f(n) este marginit ă superior de
g(n) multiplicată cu o constant ăpozitiv ăNotatia O
0204060801000200040006000800010000
f(n)= 10nlgn +5cg(n)=n2
f(n)<=cg(n)
Nu are importanț ă
comportarea pentru
valori miciale luin
n0=36O(n2)

Algoritmica -Curs 5 23Notaț iaO. Propriet ăți
1.Daca T(n)=aknk+ak-1nk-1+…+a1n+a0
atunci T(n) O(nd) pentru orice d>=k
Dem. Intrucat T(n)>0 pentru orice n, rezulta ca ak>0.
Atunci T(n)/ nk-> ak(cand n->).
Deci pentru orice ε>0 rezulta ca exista N(ε) astfel incat
T(n)/ nk<= ak+ ε pentru orice n>N(ε)
Prinurmare T(n) <= (ak+ ε)nk<= (ak+ε)nd
Considerand c=ak+ ε sin0=N(ε) rezulta ca
T(n) < cndfor all n>n0, i.e. T(n) O(nd)
Exemplu.
n O(n2)
(afirmatia este corecta insa este maiutilin practic ăsăse
considere căn O(n))

Algoritmica -Curs 5 24Notatia O. Propriet ăți
2. f(n) O(f(n)) (reflexivitate )
3. f(n) O(g(n)) , g(n) O(h(n)) => f(n) O(h(n)) (tranzitivitate )
4. (g(n)) este inclus ăîn O(g(n)
Obs. Incluziunea de maisuseste strict ă: exist ăelemente din O(g(n))
care nu aparțin lui(g(n))
Exemplu:
f(n)=10nlgn+5, g(n)=n2
f(n)<=g(n) pentru orice n>=36 f(n)O(g(n))
Dar nu existăconstante c sin0astfel incat :
cn2<= 10nlgn+5 pentru orice n >= n0

Algoritmica -Curs 5 25Notatia O. Propriet ăți
Dacăprinanalizarea celui maidefavorabil cazse obține:
T(n) <=g(n) atunci se poate spune despre T(n) căaparțineluiO(g(n))
Exemplu. Căutare secvenț ială: 6<= T(n) <= 3(n+1) ( sau
4<=T(n)<2(n+1))
Deci algoritmul căutarii secvenț ialeeste din clasa O(n)

Algoritmica -Curs 5 26Notaț iaΩ
Defini ție.
f(n)Ω(g(n)) dacăexistăc > 0 ș in0N astfel încât
cg(n) <= f(n) pentru orice n>=n0
Notaț ie.f(n)= Ω(g(n)) (ordinul de creștereal luif(n) este celpuțin la fel
de mare ca celal luig(n))
Exemple.
1. T(n) = 3n+3 T(n) Ω(n)
c=3, n0=1, g(n)=n
2. 6<= T(n) <= 3(n+1) T(n) Ω(1)
c=6, n0=1, g(n)=1

Algoritmica -Curs 5 27Nota țiaΩ
Ilustrare grafic ă. Pentru valori mari ale luin, funcțiaf(n) este marginită
inferior de g(n) multiplicată eventual de o constant ăpozitiv ă
02040608010001000200030004000
Nu are importantacg(n) <=f(n)
n0=7f(n)=10nlgn+5
cg(n)=20n
Ω(n)

Algoritmica -Curs 5 28Notatia Ω. Propriet ăți
1. Daca T(n)=aknk+ak-1nk-1+…+a1n+a0
atunci T(n) Ω(nd) pentru orice d<=k
Dem. Intruc ât T(n)>0 pentru orice n rezult ăcăak>0.
Atunci T(n)/ nk-> ak(cand n->).
Astfel pentru orice ε>0 existăN(ε) astfel încât
ak-ε <= T(n)/ nkpentru orice n>N(ε)
Rezult ăcă(ak-ε)nd<=(ak-ε)nk<=T(n)
Consider ândc=ak-ε sin0=N(ε) se obține
cnd<=T(n) pentru orice n>n0, adicăT(n) Ω(nd)
Exemplu.
n2 Ω(n)

Algoritmica -Curs 5 29Nota țiaΩ. Propriet ăți
2.(g(n)) Ω(g(n)
Dem. Este suficient săse iaîn considerare marginea inferioar ădin
defini țianotaț iei
Obs. Incluziunea este strict ă: exist ăelemente ale luiΩ(g(n)) care nu
aparțin lui(g(n))
Exemple:
f(n)=10nlgn+5, g(n)=n
f(n) >= 10g(n) pentru orice n>=1 f(n)Ω(g(n))
Dar nu existăconstante c șin0astfel încât:
10nlgn+5<= cnpentru orice n >= n0
3. (g(n))=O(g(n)) Ω(g(n)

Algoritmica -Curs 5 30Structura
•Ceeste ordinul de creștere ?
•Ceeste analiza asimptotic ă?
•Cateva notaț ii asimptotice
•Analiza eficien țeistructurilor fundamentale de
prelucrare
•Clase de eficien ță
•Analiza empiric ăa eficien țeialgoritmilor

Algoritmica -Curs 5 31Analiza eficienț eistructurilor
fundamentale de prelucrare
•Structura secven țială
A:
A1(g1(n)) O(g1(n)) Ω(g1(n))
A2(g2(n)) O(g2(n)) Ω(g2(n))
… … …
Ak(gk(n)) O(gk(n)) Ω (gk(n))
–––––––––––––––––-
(max{g1(n),g2(n), …, gk(n)})
O(max{g1(n),g2(n), …, gk(n)})
Ω(max{g1(n),g2(n), …, gk(n)})

Algoritmica -Curs 5 32Analiza eficienț eistructurilor
fundamentale de prelucrare
•Structura condi țional ă
P:
IF <conditi e>
THEN P1(g1(n)) O(g1(n)) Ω(g1(n))
ELSE P2(g2(n)) O(g2(n)) Ω(g2(n))
–––––––––––––––––––––––––
O(max{g1(n),g2(n)})
Ω(min{g1(n),g2(n)})

Algoritmica -Curs 5 33Analiza eficienț eistructurilor
fundamentale de prelucrare
• Prelucrarea repetitiv ă
P:
FOR i ←1, n DO
P1 (1)  (n)
FOR i ←1,n DO
FOR j ← 1,n DO
P1 (1)  (n2)
Obs: In cazul a k cicluri suprapuse a cărorcontor variaz ăîntre1 șin
ordinul de complexitate este nk

Algoritmica -Curs 5 34Analiza eficienț eistructurilor
fundamentale de prelucrare
Obs.
Dacălimitele contorului sunt variabile atunci numărulde operaț ii
efectuate trebuie calculat explicit pentru fiecare dintre ciclurile
suprapuse
Exemplu:
m← 1
FOR i← 1,n DO
m← 3*m {m=3i}
FOR j ← 1,m DO
prelucrare de cost (1)
Ordinul de complexitate al prelucr ăriieste:
3+32+…+3n = (3n+1-1)/2-1
adica(3n)

Algoritmica -Curs 5 35Structura
•Ceeste ordinul de creștere ?
•Ceeste analiza asimptotic ă?
•Cateva notaț ii asimptotice
•Analiza eficien țeistructurilor fundamentale de
prelucrare
•Clase de eficien ță
•Analiza empiric ăa eficien țeialgoritmilor

Algoritmica -Curs 5 36Clase de eficienț ă
Câteva dintre cele maifrecvente clase de eficien ță(complexitate):
Nume clasa Nota ție
asimptoticaExemplu
logaritmic O(lgn) Căutare binar ă
liniar O(n) Căutare secven țială
patratic O(n2) Sortare prininser ție
cubic O(n3) Inmul țireaa douămatrici nxn
exponential O(2n) Prelucrarea tuturor submultimilo r
unei mulțimicu n elemente
factorial O(n!) Prelucrarea tuturor permut ărilor
de ordin n

Algoritmica -Curs 5 37Exemplu
Se considera un tablou cu n elemente, x[1..n] avand valori din
{1,…,n}. Tabloul poate avea toate elementele distincte sau
poate exista o pereche de elemente cu aceeasi valoare (o
singur ăastfel de pereche). Săse verifice dacăelementele
tabloului sunt toate distincte sauexistăo pereche de elemente
identice.
Exemplu: n=5, x=[2,1,4,1,3] nu are toate elementele distincte
x=[2,1,4,5,3] are toate elementele distincte
Se pune problema identific ăriiunui algoritm cât maieficient din
punct de vedere al timpului de execuț ie

Algoritmica -Curs 5 38Exemplu
Varianta 1:
verific (x[1..n])
i←1
d ← True
while (d=True) and ( i<n) do
d←NOT ( caut(x[i+1..n],x[i ]))
i← i+1
endwhile
return d
Dim. problemei : n
1<= T(n)<=T’(n -1)+T’(n -2)+…+T’(1)
1<=T(n)<=n(n -1)/2
T(n) Ω(1), T(n) O(n2)caut(x[s..f],v)
i← s
while x[i]<>v AND i<f do
i← i+1
endwhileif x[i]=v then return True
else return False
endifDim. subproblemei : k=f-s+1
1<= T’(k)<=k
Cazfavorabil : x[1]=x[2]
Cazdefavorabil : elemente
distincte

Algoritmica -Curs 5 39Exemplu
Varianta 2:
verific(x[1..n])
Integer f[1..n] // tabel frecvente
f[1..n] ← 0
for i ← 1 to n do
f[x[i]] ←f[x[i]]+1
i ← 1
while f[i]<2 AND i<n do i ← i+1
if f[i]>=2 then return False
else return True
endifDimensiune problema: n
n+1<= T(n)<=2n
T(n) (n) Varianta 3:
verific3(x[1..n])Integer f[1..n] // tabel frecventef[1..n] ← 0
i ← 1
while i<=n do
f[x[i]] ← f[x[i]]+1
if f[x[i]]>=2 then return False
i ← i+1
endifendwhilereturn True
Dimensiune problema: n
4<= T(n)<=2n
T(n) O(n) , T(n) Ω(1)

Algoritmica -Curs 5 40Exemplu
Varianta 4:
Variantele 2 si 3 necesita un
spatiu suplimentar de
memorie de dimensiune n
Se poate rezolva problema in
timp liniar dar fara a utiliza spatiu suplimentar de dimensiune n ci doar de dimensiune 1?
Idee: elementele sunt distincte
doar daca in tablou se afla toate elementele din multimea {1,2,…,n} adica suma lor este n(n+1)/2verific4(x[1..n])s←0
for i← 1 to n do s←s+x [i] endfor
if s=n(n+1)/2 then return True
else return False
EndifDimensiune problema: nT(n) = n
T(n) (n)
Obs.
Varianta 4 este maibună decât
varianta 3 în raport cu spațiulde
memorie utilizat însăîn cazul mediu
timpul de execuț ieeste maimic în
varianta 3 decât în varianta 4

Algoritmica -Curs 5 41Structura
•Ceeste ordinul de creștere ?
•Ceeste analiza asimptotic ă?
•Cateva notaț ii asimptotice
•Analiza eficien țeistructurilor fundamentale de
prelucrare
•Clase de eficien ță
•Analiza empiric ăa eficien țeialgoritmilor

Algoritmica -Curs 5 42Analiza empiric ăa eficienț eialgoritmilor
Uneori analiza teoretic ăa eficien țeieste dificilă ; în aceste cazuri
poate fiutilă analiza empiric ă.
Analiza empiric ăpoate fiutilizat ăpentru:
•Formularea unei ipoteze inițialeprivind eficien ța algoritmului
•Compararea eficien țeia maimultor algoritmi destinaț irezolv ării
aceleiaș iprobleme
•Analiza eficien țeiunei implement ăria algoritmului (peo anumit ă
mașina)
•Verificarea acurateț ii unei afirma ții privind eficien ța algoritmului

Algoritmica -Curs 5 43Structura general ăa analizei
empirice
1. Se stabile ștescopul analizei
2. Se alege o măsurăa eficien ței(de exemplu, numărulde execuț ii ale
unor operaț ii sautimpul necesar execuț ieiunor pașide prelucrare)
3. Se stabilesc caracteristicile setului de date de intrare cevafiutilizat
(dimensiune, domeniu de valori …)
4. Se implementeaz ăalgoritmul sauîn cazul in care algoritmul este
deja implementat se adaugă instruc țiunile necesare efectuă rii
analizei (contoare, funcții de înregistrare a timpului necesar execuț iei
etc)
5. Se genereaz ădatele de intrare
6. Se execut ăprogramul pentru fiecare datăde intrare șise
înregistreaz ărezultatele
7. Se analizeaz ărezultatele obținute

Algoritmica -Curs 5 44Structura general ăa analizei
empirice
Măsura eficien ței: este aleas ăîn funcțiede scopul analizei
• Dacăscopul este săse identifice clasa de eficien țăatunci se poate
folosi numărulde operaț ii care se execut ă
• Dacăscopul este săse analizeze/compare implementarea unui
algoritm peo anumita mașinade calcul atunci o măsura adecvat ăar
fitimpul fizic

Algoritmica -Curs 5 45Structura general ăa analizei
empirice
Set de date de intrare. Trebuie generate diferite categorii de date de
intrare pentru a surprinde diferitele cazuri de funcționare ale
algoritmului
Câteva reguli de generare a datelor de intrare:
• Datele de intrare trebuie săfie de diferite dimensiuni șicu valori cat
maivariate
• Setul de test trebuie săconținădate cât maiarbitrare (nu doar
excepț ii)

Algoritmica -Curs 5 46Structura general ăa analizei
empirice
Implementarea algoritmului .De regul ăeste necesar ăintroducerea unor
prelucr ăride monitorizare
• Variabile contor (în cazul in care eficien ța este estimat ăfolosind
numărulde execuț ii ale unor operaț ii)
• Apelul unor funcții specifice care returneaz ăoracurent ă(în cazul în
care măsuraeficien țeieste timpul fizic)

Algoritmica -Curs 5 47Următorul curs vafidespre…
… algoritmi de sortare
… analiza corectitudinii lor
… analiza eficien ței