(290181372) PA_2

7/18/2019 (290181372) PA_2

http://slidepdf.com/reader/full/290181372-pa2 1/46

Proiectarea algoritmilor

Analiza complexităţii algoritmilor

7/18/2019 (290181372) PA_2


Scopul analizei

2

Aprecierea calităţii unui algoritm, prindeterminarea resurselor necesare pentruexecuţia algoritmului pe o maşină de calcul.

Prin resurse necesare se înţelege: Spaţiul maxim de memorie necesar pentru

execuţia algoritmului. Trebuie luată în consideraresituaţia alocării dinamice a memoriei, cândaceasta poate avea valori dierite în puncte dieriteale algoritmului.

Timpul necesar pentru execuţia tuturor operaţiilor cuprinse în algoritm.

7/18/2019 (290181372) PA_2


Volumul de resurse

!n ma"oritatea situaţiilor, volumul de resurse necesar pentru execuţia unui algoritm depinde de dimensiuneaproblemei de re#olvat.

Aceasta este determinată, în principal, de volumul

datelor de intrare. !n ca#ul cel mai general acest lucru este dat numărul

de biţi necesari pentru memorarea datelor. $acă se prelucrea#ă o valoare numerică, n %de ex.

dacă se veriică că numărul n este prim& atunci cadimensiune a problemei se consideră numărul de biţinecesari pentru repre#entarea lui n, adică 'log(n)*+.

7/18/2019 (290181372) PA_2


Dimensiunea problemei

neori dimensiunea problemei depinde detipul prelucrării. $e exemplu la prelucrarea unui text, dacă

prelucrările se ac la nivel de cuvânt, dimen-siunea problemei este dată de numărul decuvinte.

$acă prelucrările se ac la nivel de caracter

atunci dimensiunea problemei este dată denumărul de caractere.

7/18/2019 (290181372) PA_2


Spaţiul de memorie

5

Spaţiul de memorie necesar pentru memorareadatelor este inluenţat de modul de repre#entareadatelor.

$e exemplu o matrice + x + care are numai /

de elemente nenule %matrice rară& poate i memorată în mai multe eluri:0 Tablou + x +, cu + locaţii de memorie.0 Tablou / x 1, cu trei coloane, indicând linia,coloana şi valoarea.

2e#ultă +/ de locaţii de memorie.

7/18/2019 (290181372) PA_2


Timpi de execuţie

3otăm cu T(n) timpul de execuţie al unui algoritmpentru re#olvarea unei probleme de dimensiune n. Pentru a stabili timpul de execuţie trebuie propus un

model de calcul şi o unitate de măsură.

4om considera un model de calcul %numit şi maşină decalcul cu acces aleator& caracteri#at prin: prelucrările se eectuea#ă în mod secvenţial5 operaţiile elementare se execută în acelaşi timp

indierent de valoarea operan#ilor5 timpul de acces la o inormaţie nu depinde de po#iţia

acesteia %de exemplu, într-un şir de caractere timpulde acces este acelaşi pentru orice element din şir&5

7/18/2019 (290181372) PA_2


Unitate de măsură

Se stabilesc operaţiile elementare şi seconsideră ca unitate de măsură timpul deexecuţie a acestora.

Timpul total de execuţie va i dat de număruloperaţiilor elementare.6peraţiile elementare sunt cele aritmetice

%adunare, scădere, înmulţire, împărţire&,comparaţiile între două valori, operaţiile logice%A3$ , 62 , 36T&.

7/18/2019 (290181372) PA_2


Scopul calculului timpului de execuţieeste acela de a compara calitateaalgoritmilor5

Timpul de execuţie al întreguluialgoritm se obţine însumând timpii de

execuţie a prelucrărilor componente.

7/18/2019 (290181372) PA_2


7ste suicient uneori să se contori#e#e

doar anumite tipuri de operaţii elementare,numite operaţii de bază;

$e exemplu în operaţii de sortare se potconsidera doar operaţiile de comparare şi

mutare a elementelor& şi8sau să seconsidere că timpul de execuţie a acestoraeste unitar %este acelaşi pentru toateoperaţiile5

Se ştie că operaţiile de înmulţire şi împărţire sunt mai costisitoare ca cele deadunare sau scădere&.

7/18/2019 (290181372) PA_2


Exemplu:Calculului Σ i, i=1,..n

10

$imensiunea acestei probleme este n. Algoritmul de re#olvare este:

Suma ( n)

1: S ← 0

2: i ← +3: WHIL i ! n "#

$: S ← S % i &: i ← i% +'T' S

7/18/2019 (290181372) PA_2


În algoritmul de mai sus operaţiile care sunt contorizate suntnumerotate.Timpul de execuţie al algoritmului poate fi determinat folosind

taelul de costuri:6peraţie 9ost 3r. repetări

+ c+ +( c( +

1 c1 n*+

c n

/ c/ n

7/18/2019 (290181372) PA_2


12

Însum!nd timpii de execuţie se oţine:

T(n) * +1% +2%n,( +3% +$% +&)% +3 *;n,( +3% +$% +&)%+1%+2%+3*-1,n%-2

Adică, timpul de execuţie este propor-

ţional cu dimensiunea problemei.Se observă că valoarea costurilor

operaţiilor elementare inluenţea#ă doar

constantele care intervin în T(n).

7/18/2019 (290181372) PA_2


Prelucrarea repetitivă de mai sus poate i înlocuită cu+. . ←0

(. <62 i ← n,+ $63/ . ← .%i;

'T' .;

!n acest ca#, T(n) ; +1% +2 %+3

/

(n%1)%n,+&/ $e remarcat că instrucţiunea <62 se repetă de

n*+ ori, datorită controlului limitelor pentru contor. $acă incrementarea lui i şi controlul depăşirii valorii

n au acelaşi cost %; +&, atunci ciclul <62 costă(=%n*+&, pentru o buclă care se repetă de n ori.

7/18/2019 (290181372) PA_2


Exemplul "C#m,p$=%#m,n$ & '#n,p$

!n acest ca# dimensiunea problemei estedată de trei valori (mnp).

rodu. (a b m n p)1/ or i*1m "o2/ or *1p "o3/ +4i5 ← 0

$/ or -*1n "o&/ +4i5 ← +4i5% a4i-56b4-5;

'e7urn +;

7/18/2019 (290181372) PA_2


1(

9ostul prelucrărilor de peliniile +,( şi repre#intă

costul gestiunii contorului şiva i tratat global.Presupunând că toate

operaţiile aritmetice şi decomparare au acelaşi cost

unitar, tabelul costuriloreste:

2e#ultă timpul de execuţie:

T(m,n,p)=4mnp+5mp+4m+2

6peraţie 9ost 3r. repetări

+ (%m*+& +

( (%p*+& m

1 + mp

(%n*+& mp

/ ( mpn

7/18/2019 (290181372) PA_2


16

!n practică nu este necesară o anali#ă atâtde detaliată, ci este suicient să seidentiice operaţia de ba#ă şi să seestime#e numărul de repetări ale acestuia.

Prin operaţia de ba#ă se înţelege operaţiacare contribuie cel mai mult la timpul deexecuţie al algoritmului şi este operaţia ceapare în ciclul cel mai interior.

!n exemplul de mai sus se poate consideraca operaţie de ba#ă operaţia de înmulţire.

!n acest ca# costul execuţiei algoritmului ar i: T(nmp)*m,n,p.

7/18/2019 (290181372) PA_2


Timpul mediu de execuţie 2epre#intă valoarea medie a timpul de execuţie al unui

algoritm atunci când datele de intrare sunt reparti#ateprobabilistic pe domeniul lor de existenţă.

$acăυ )n*

repre#intă numărul variantelor posibile pentru

datele de intrare, P> repre#intă probabilitatea de apariţie avariantei >, iar T>%n& repre#intă timpul de execuţiecorespun#ător variantei >, atunci timpul mediu de execuţieeste dat de relaţia:

T m)n*

υ )n*

= ∑T k)n* P

k

k =1

7/18/2019 (290181372) PA_2


+ac toate cazurile sunt ec-iproaile, atunci:

P k= 1 ,

k

υ)n*

= 1,",..,υ)n*

υ

) n *

∑T k )n*

T )k * = k =1

m

υ )n*

7/18/2019 (290181372) PA_2


Exemplu Problema căutării unei valori într-un şir 8

1 8

2

//8 n de elemente distincte. 4om calcula timpul mediu în ipote#a că

valoarea v se poate ala în oricare din po#iţiile

din şir cu aceeaşi probabilitate. Pentru că avem n ca#uri pentru po#iţionarea în şir şi încă un ca# în care valoarea nu se ală în şir, atunci

ν )n* = n +1

7/18/2019 (290181372) PA_2


ezult:

Timpul corespun#ător ca#ului în care valoarea vse ală pe po#iţia > este: T>%n&; /%>*+&,iar timpul pentru ca#ul în care valoarea v nu seală în şir este:

Tn%n*+&; /%n*+&.

7/18/2019 (290181372) PA_2


"1

7/18/2019 (290181372) PA_2


Problema principală în asemenea situaţii o

22

constituie stabilirea distribuţiei datelor de intrare.

$e exemplu, pentru problema de mai sus s-ar puteaconsidera şi ipote#a:

- p;./ ? valoarea v se ală în tablou, iar probabilitateade a se ala pe oricare din po#iţiile din şir este aceeaşi

? +8n- p;./ ? valoarea v nu se ală în tablou !n acest ca#, timpul mediu de execuţie este:

7/18/2019 (290181372) PA_2


Se constată că timpul mediu de execuţiedepinde de ipote#ele acceptate pentru datele

de intrare şi nu este o medie aritmetică întretimpul corespun#ător ca#ului cel maineavorabil şi cel corespun#ător ca#ului celmai avorabil.

7/18/2019 (290181372) PA_2


Ordin de crestere

Pentru a aprecia eicienţa unui algoritm nueste necesară cunoaşterea exactă a expre-siei timpului de execuţie.

@nteresea#ă mai mult modul în care varia-#ă timpul de execuţie o dată cu creştereadimensiunii problemei.

6 măsură utilă în acest sens este ordinul

de +re97ere.

7/18/2019 (290181372) PA_2


Acesta este determinat de termenuldominant din expresia T%n& în uncţiede dimensiunea n a problemei.

7ste "ustiicat de aptul că pentru nmare, termenii dieriţi de cel dominantsunt negli"abili.

7/18/2019 (290181372) PA_2


Exemplul 1

$acă T(n) * a,n % b %a & atunci lacreşterea lui n de > ori, termenul dominantcreşte şi el de > ori,

T(-,n) * a,-,n % b.

!n acest ca# avem o dependenţă liniară aordinului de creştere.

7/18/2019 (290181372) PA_2


Exemplul "

$acă T(n) * a,n2 % b,n%+ %a & atunci lacreşterea lui n de > ori, termenul dominantcreşte de - 2 ori,

T(-,n) * a,- 2 ,n2 % b,-,n%+ . !n acest ca# avem o dependenţă pătratică a

ordinului de creştere.

7/18/2019 (290181372) PA_2


Exemplul /

$acă T(n) * a,l n, atunci T%>=n& ; a,l n %a,l - adică în acest

ca# termenul dominant nu semodiică, timpul de execuţie crescândcu o constantă.

Să preci#ăm că prin l n înţelegemlog( n.

7/18/2019 (290181372) PA_2


Exemplul 0

"

$acă T(n) * a,2 n atunci

T(-,n) * a,2 - ,2 n* a,(2 n )- adicătermenul dominant creşteexponenţial.

7/18/2019 (290181372) PA_2


30

!ntrucât problema eicienţei este importantăla valori mari ale lui n %teoretic n B C&,anali#a complexităţii interesea#ă doar înasemenea situaţii.

9onsiderarea numai a termenuluidominant. Acest tip de anali#ă ; analiză a.imp7o7i+ă. !n cadrul anali#ei asimptotice se consideră

că un algoritm este mai eicient decât altuldacă ordinul de creştere al timpului deexecuţie al primului este mai mic decâtordinul de creştere al celui de-al doilea.

7/18/2019 (290181372) PA_2


2elaţia între ordinele de creştere are

semniicaţie doar pentru dimensiuni mariale problemei. $acă considerăm timpii:

T 1(n) * 10,n % 10 9i T

2 (n) * n2 , atunci se observă cu uşurinţă c

T 1(n) T 2 (n) pentru n ! 10 , deşi ordinul de

creştere al lui T 1 este mai mic decât al luiT

2 .

7/18/2019 (290181372) PA_2


Notaţii asimptotice- gruparea alg. în clase în

functie de timpii de execuţie

1. Notaţia Θ Pentru o funcţie g: N→R

+

espre timpul de execuţie al unui algoritm! T(n)!spunem că este Θ(g(n)) dacă "#n$ % Θ(g(n))

7/18/2019 (290181372) PA_2


!n practică se mai oloseşte notaţiaabu#ivă

T(n)* <((n))/

Practic, prin notaţia =(n) >

(n) înseamnă că =(n) şi (n)sunt asimptotic ecDivalente.

7/18/2019 (290181372) PA_2


34

2atematic, acest lucru se traduce prin:

7xemplu: Să considerăm uncţia =(n)*n2 %&,n,l:n%10 şi (n)*n2 .9u constantele c+;+ şi c(; vom veriica graicpentru ce valori ale lui n, are loc inegalitatea

7/18/2019 (290181372) PA_2


!n ig. sunt repre#entate cele 1 uncţii pentrun E + - <ig.+

7/18/2019 (290181372) PA_2


&ele ' funcţii pentru n ( )*. + ,ig.

/3

7/18/2019 (290181372) PA_2


4ser5aţii

37

$in ig.+ se poate vedea că este suicient săconsiderăm n n; pentru ca relaţia

E c+g%n& E %n& E c(g%n&

să ie respectată. Pentru valori mari, aşa cum re#ultă din ig.(,

condiţia este respectată.

7/18/2019 (290181372) PA_2


Notaţia O

Pentru o uncţie g: 3B2*,

6%g%n&& repre#intămulţimea de uncţii:

Aceasta permite descrierea comportării unuialgoritm în ca#ul cel mai deavorabil, ără a se

ace reerire la celelalte situaţii.

7/18/2019 (290181372) PA_2


!ntrucât interesea#ă comportareaalgoritmului pentru date arbitrare, estesuicient să speciicăm o margine

superioară pentru timpul de execuţie. $acă =(n) > #((n)) înseamnă că =(n)

creşte asimptotic la el de repede ca g%n&.

7/18/2019 (290181372) PA_2


%dic: 6 78

$in deiniţiile lui < 9i # re#ultă că

<((n)) ⊂#((n)) inclu#iunea iind strictă.

Prin urmare dacă T%n&; F%g%n&& atunci

T%n&; 6%g%n&&

,

7/18/2019 (290181372) PA_2


3otaţia G

Pentru o uncţie g: 3B2*, G%g%n&& repre#intămulţimea de uncţii:

7/18/2019 (290181372) PA_2


Această uncţie este o măsură a ordinului decreştere a timpului de execuţie în ca#ul cel maiavorabil5

$acă înseamnă că %n& creşteasimptotic cel puţin la el ca g%n& adică:

, >, iar limita putând i şiininită.

7/18/2019 (290181372) PA_2


0/

7/18/2019 (290181372) PA_2


&lase de complexitate

!n ierarDi#area algoritmilor după ordinul decomplexitate se ţine cont de următoareleproprietăţi ale uncţiilor ce intervin cel mai

recvent în anali#ă:

00

7/18/2019 (290181372) PA_2


0(

7/18/2019 (290181372) PA_2


/ser0aţie

Algoritmii din clasele exponenţială şiactorială pot i utili#aţi doar pentru problemede dimensiune mică.

(290181372) PA_2

Documents

Transcript of (290181372) PA_2