complexitatea algoritmilor 2

Complexitatea algoritmilor

Tehnici Avansate de Programare

INFO II, III

2010-2011

Algoritm

Def:

O metodă efectivă de rezolvare a unei probleme.

Obs:

1. Problema determină algoritmul.

2. Ce înseamnă efectivă?

3. Dacă există mai mulţi algoritmi, pe care îl aleg?

Algoritm

Obs:

1. Problema determină algoritmul.

Pentru probleme diferite, se presupune că se găsesc algoritmi diferiţi.

Alternativ: General Problem Solver (GPS)

aplicaţie creată în 1957 de H. Simon, J.C. Shaw şi A. Newell

Newell, A.; Shaw, J.C.; Simon, H.A. (1959). Report on a general problem-solving program. Proceedings of the International Conference on Information Processing. pp. 256-264.

Algoritm

Obs:2. Ce înseamnă efectivă?Indiferent de interacţiunile cu mediul (date de intrare, valori generate, evenimente externe) algoritmul este o listă finită, bine-definită de paşi.

Există programe fără date de intrare?Da, rezolvă o singură instanţă.

Valori generate: generatoare de numere aleatoare.Exemplu de eveniment extern: depăşirea timpului

alocat pentru un transfer de date în reţea.

Algoritm

Obs:3. Dacă există mai mulţi algoritmi, pe care îl

utilizez?

Definesc o măsură şi îi compar. Măsuri funcţionale (numerice, cantitative): cât timp

este necesar, câtă memorie este necesară?Unitatea de măsură: o comparaţie, o atribuire, un octet…

Măsuri nefuncţionale (nenumerice, calitative, descrise de Ingineria Programării): (anul III!!!)

Proprietăţile algoritmilor

Corect:rezolvă problema propusă.

Finit:se încheie întotdeauna (în lipsa întreruperilor externe).

General:rezolvă mai multe instanţe (seturi diferite de date de intrare).

Determinist:la execuţii repetate în aceleaşi condiţii evoluează identic.

Analiza algoritmilor

1. Găsesc invarianţe (momente în evoluţie când este întotdeauna îndeplinită o proprietate).

2. Arăt că: dacă e finit, atunci rezolvă problema.3. Arăt că: este finit.4. Arăt că: este cât mai eficient (optim de

preferinţă).

Exemplu: Sortarea prin interschimbare for each i in 0 to n – 2 for each j in i + 1 to n - 1 if A[i] > A[j] then swap(A[i], A[j]) end for end for


Exemplu de analiză: Sortarea prin interschimbare 1. InvarianţăDupă fiecare comparare cu ultimul element al vectorului, cel mai mic element

din fragmentul prelucrat ajunge pe poziţia corectă.

2. Dacă e finit, atunci rezolvă problemaLa sfârşit, după cele n -1 treceri prin vector se aşează corect primele n -1

elemente; vectorul este deci sortat; problema este rezolvată.

3. Este finitSunt 2 structuri repetitive for (cu număr a-priori cunoscut de paşi) imbricate,

deci secvenţa internă se execută de un număr finit de ori.


Exemplu de analiză : Sortarea prin interschimbare

(cont.) 4. Eficienţă Se alege operaţia elementară: atribuirea.

Se numără atribuirile, în funcţie de lungimea vectorului de sortat:

Dacă operaţia elementară este comparaţia?

Dar interschimbarea (swap)?

Optimalitate – Nu se pune problema (încă).

2

0

1

1

2 72))31(1()(n

i

n

ij

nnnt

Analiza algoritmilorDef:Ordinul lui f: N →R este: Mulţimea funcţiilor asimptotic mărginite superior

de un multiplu pozitiv al lui f (upper bounds).

De ce? Pentru că există algoritmi pentru care datele de intrare influenţează numărul de operaţii elementare (ex.: numărul de interschimbări pentru Sortarea prin interschimbare).

Altă exprimare: “este de tip O-mare (big O)”.

))}()()()()((|:{)( 00 ncfntnnNnRcRNtfO

Analiza algoritmilorOrdinul lui f: N →R

Pentru că t(n) depinde de instanţă, căutăm o funcţie f majorantă, dar cu expresie invariantă.

Imagine de la http://www.csanimated.com/animation.php?t=Big_O_notation

http://www.csanimated.com/animation.php?t=Big_O_notation





)}2)()()()((|:{)2(

)})()()()((|:{)(

))}log()()()()((|:{))log((

)})()()()((|:{)(

)})()()()((|:{)1(

00

200

2

00

00

00

nn cntnnNnRcRNtO

cnntnnNnRcRNtnO

ncnntnnNnRcRNtnnO

cnntnnNnRcRNtnO

cntnnNnRcRNtO

Ordinul lui f: N →R Exemple:

Ierarhie de ordine:

Este de dorit un algoritm de ordin cât mai în stânga.

)2()())log(()()1( 2 nOnOnnOnOO

Analiza algoritmilorOrdinul lui f: N →R Convenţie, Exemple şi Proprietăţi: în loc de

Exprimarea “t(n) este cel mult O(…)” este incorectă pentru că O(…) descrie per se (în sine) o margine superioară.

http://www.csanimated.com/animation.php?t=Big_O_notation pentru o prezentare animată

)(145

)()()(145

)()()(145

)()()(145

2

222

332

2372

nOnn

nOngnOnn

ngnntnOnn

nOnntnOnn

))(()( nfOnt ))(()( nfOnt


Analiza algoritmilorDef: Dată f: N →R, mulţimea funcţiilor asimptotic

mărginite inferior de un multiplu pozitiv al lui f (lower bounds):

Comportarea asimptotică este dată de (tight bounds):

Alte exprimări: “este de tip omega-mare (big Ω); teta-mare (big Φ)”.

Aceste trei notaţii fac parte din categoria notaţiilor Bachmann-Landau.

)()()( ffOf

))}()()()()((|:{)( 00 ntncfnnNnRcRNtf

Analiza algoritmilorΦ(f)

Pentru că t(n) depinde de instanţă, căutăm o funcţie f care multiplicată cu două constante

“înconjoară” pe t şi care are expresie invariantă.

Analiza algoritmilorExemple şi Proprietăţi:

)(3)log(

)(62

)(173

)(32

1

2

23

2

22

nnn

nn

nn

nnn

)()(

)())log((

)(

))(log(2

fggOf

nnn

nn

nn

Exemplu

Care este complexitatea algoritmului următor? Exprimaţi prin cele 3 notaţii.

val = 0 for i = 1 to n for j = 1 to n^2 for k = 1 to n^3 val = val + 1

endfor

endfor

endfor


Exemplu

Care este complexitatea algoritmului următor? Exprimaţi prin cele 3 notaţii.

sum = 0;

for (j = 1; j < n; j* = 2) {

sum++;

}


Analiza algoritmilorExemple şi Proprietăţi:Dacă operaţia elementară se execută de un număr

constant de ori, atunci complexitatea este O(1) (constantă):

• for ( i = 0; i < 5; i++ ) statement; • for ( i = 0; i < k; i++ ) statement;• statement;

Dacă operaţia elementară se execută de n ori într-un for, atunci complexitatea este O(n) (liniară):

• for ( i = 0; i < n; i++ ) statement; • for ( i = 0; i < n; i++ )

if ( test_cond) statement;• for ( i = 0; i < n; i = i + 2 ) statement;

Analiza algoritmilorExemple şi Proprietăţi:Dacă operaţia elementară se execută în două for imbricate,

atunci complexitatea este O(n2) (pătratică):for ( i = 0; i < n; i++ )

for ( j = 0; j < n; j++ ) statement;

Dacă operaţia elementară se execută prin înjumătăţirea lui n, atunci complexitatea este O(log(n)) (logaritmică):low = 0;high = n – 1;while ( low <= high ) {

mid = ( low + high ) / 2; if ( target < list[mid] ) high = mid - 1; else if ( target > list[mid] ) low = mid + 1; else break;

}(Pentru că se realizează de k ori, unde n=2k)


Aproximarea Stirling pentru log(n!):log(n!) = n*log(n) - n + O(log(n))

Formula Ramanujan pentru log(n!) – exactă!log(n!) = n*log(n) - n + log(n*(1+4*n*(1+2*n)))/6 + log(PI)/2

dacă n > 20

Deci O(log(n!)) = O(n log(n))

Ramanujan, Srinivasa (1988), The lost notebook and other unpublished papers, Springer Berlin, p. 339, ISBN

354018726X


Automatizarea analizei (trasare – profiling)

1. Expandare (augmentation)

instrucţiuni suplimentare

2. Execuţie (execution)

rezultate scrise în fişiere speciale

3. Analiza (analysis)

analiza fişierelor rezultate


Automatizarea analizei (trasare – profiling)Exemplu pentru atribuiri

count = 0for each i in 0 to n – 2

count++ for each j in i + 1 to n – 1

count++ if A[i] > A[j] then

swap( A[i], A[j] )count+=3

end for end for

Fără probleme



Exemplu pentru timpbegin_time = clock()

for each i in 0 to n – 2

for each j in i + 1 to n – 1

if A[i] > A[j] then swap( A[i], A[j] )

end for

end for

end_time = clock()

needed_time = end_time - begin_time

Apar probleme



Exemplu pentru timp

Apar probleme: Granularitatea ceasului introduce erori (unele execuţii se fac în timp zero).Testaţi codul şi comparaţi cu frecvenţa procesorului:

void test() {

for ( int i = 0; i <100; i++)

cout << "clock() = " << clock() << "\n";

}

Rezolvare (parţială): Se realizează execuţii multiple şi se calculează media aritmetică.


Automatizarea analizei (trasare – profiling)Exemplu pentru timp

begin_time = clock()for k in 1 to nexec

reset A for each i in 0 to n – 2 for each j in i + 1 to n – 1

if A[i] > A[j] then swap(A[i], A[j]) end for

end forend forend_time = clock()needed_time = (end_time - begin_time) / nexec



Exemplu pentru timp

De ce parţială?

Se introduc suplimentări de timp prin resetarea lui A.

Altă rezolvare (tot parţială): se consideră doar aplicaţia originală la captarea timpului.


Automatizarea analizei (trasare – profiling)Exemplu pentru timp

needed_time = 0for k in 1 to nexec

reset A begin_time = clock()for each i in 0 to n – 2 for each j in i + 1 to n – 1

if A[i] > A[j] then swap( A[i], A[j] ) end for

end forend_time = clock()needed_time += (end_time - begin_time)

end forneeded_time /=nexec



Exemplu pentru timp

De ce tot parţială?

Se preiau neajunsurile de la trasarea iniţială.

Alte probleme, în cazul unui algoritm oarecare:

Numărul de operaţii elementare poate depinde de datele de intrare.


Automatizarea analizei (trasare – profiling)Exemplu pentru timpBubble-sort: operaţia elementară este

interschimbarea (swap) do swapped = false for each i in 1 to n - 1 if A[i - 1] > A[i] then

swap(A[i - 1], A[i]) swapped = true

end for while swapped


Automatizarea analizei (trasare – profiling)Numărul de instrucţiuni elementare poate depinde

de datele de intrare.

Se studiază cazurile:• cel mai favorabil (consum minim de resurse)• mediu (statistica pentru toate cazurile – se

generează toate instanţele – uneori infezabil)• cel mai nefavorabil (consum maxim de

resurse)


Analiză teoretică:

Sortarea prin comparaţie (orice sortare în care se compară perechi de elemente, în mod repetat)

Operaţia elementară: comparaţia.

Se poate un ordin de sortare prin comparaţie < O(n log(n)) în cazul cel mai nefavorabil ?

NU


Analiză teoretică.Instrucţiune elementară: comparaţia.Arborele de decizie: binar, nodul are o

comparaţie, frunza este o permutare.

Imagine din “Tehnici de Proiectarea şi Analiza Algoritmilor”Dorel Lucanu,Facultatea de Informatică Iaşi.

Desenaţi cazul n = 4.


Analiză teoretică.Instrucţiune elementară: comparaţia.

O listă cu n elemente distincte se sortează în f(n) comparaţii.

Dacă f(n) este minim, atunci arborele de decizie trebuie să fie echilibrat (arbore AVL*).

Un arbore echilibrat pe f(n) niveluri are cel mult 2f(n) frunze.n!< 2f(n) deci f(n)>log(n!) deci f(n) are cel puţin ordinul O(n log(n))

* Adelson-Velskii, G.; E. M. Landis (1962) "An algorithm for the organization of information". Proceedings of the USSR Academy of Sciences 146: 263–266. (Russian) English translation by Myron J. Ricci in Soviet Math. Doklady, 3:1259–1263


Analiză teoretică.

Instrucţiune elementară: comparaţia.

Există sortări cu O(n log(n)) în cazul cel mai nefavorabil?

DA

care???

complexitatea algoritmilor 2

Documents