Notiunea de algoritm. Analiza algoritmilor

1. Notiunea de algoritm

• Termenul algoritm isi are sorgintea in numele autorului persan Abu Ja'far Mohamed Ibn Musa Al Khowarismi care in anul 825 i.e.n. a redactat un tratat de matematica in care prezenta pentru prima data metode de rezolvare generice pentru anumite categorii de probleme.

• Dictionarul explicativ al limbii romane [DEX75] ofera urmatoarea definitie: 'Ansamblu de simboluri si de operatori, folositi in matematica si logica, permitand gasirea in mod mecanic (prin calcul) a unor rezultate'.

• Alte dictionare ofera alte definitii, spre exemplu: 'Orice metoda de rezolvare a unei anumite probleme'.

• In activitatea de programare vom conveni ca prin algoritm sa intelegem o 'modalitate de rezolvare a unei probleme utilizand un sistem de calcul'

• Un algoritm este de fapt o metoda sau o reteta pentru a obtine un rezultat dorit.

• Un algoritm consta din:

• Un set de date initiale care abstractizeaza contextul problemei de rezolvat

• Un set de relatii de transformare care sunt operate pe baza unor reguli al caror continut si a caror succesiune reprezinta insasi substanta algoritmului

• Un set de rezultate preconizate sau informatii finale, care se obtin trecand de regula printr-un sir de informatii (rezultate) intermediare.

• Un algoritm se bucura de urmatoarele proprietati:

• Generalitate - un algoritm nu rezolva doar o anume problema ci o clasa generica de probleme de acelasi tip;

• Finitudine - informatia finala se obtine din cea initiala trecand printr-un numar finit de transformari;

• Unicitate - transformarile si ordinea in care ele se aplica sunt univoc determinate de regulile algoritmului. Ori de cate ori se aplica acelasi algoritm asupra aceluiasi set de date initiale se obtin aceleasi rezultate.

Scopul capitolului analiza performantei algoritmilor.

Analiza algoritmilor

• La ce serveste analiza algoritmilor ?

• Permite precizarea predictiva a comportamentului algoritmului;

• Prin analiza pot fi comparati diferiti algoritmi si poate fi astfel ierarhizata experienta si indemanarea diversilor producatori [HS78].

• Analiza algoritmilor se bazeaza de regula pe ipoteze:

• Sistemele de calcul sunt considerate conventionale adica ele executa cate o singura instructie la un moment dat

• Timpul total de executie al algoritmului rezulta din insumarea timpilor instructiilor individuale componente.

• Desigur aceasta ipoteza nu este valabila la sistemele de calcul paralelele si distribuite.

In astfel de cazuri aprecierea performantelor se realizeaza de regula prin masuratori experimentale si metode statistice.

In general, analiza unui algoritm se desfasoara in doua etape:

o      (1) Analiza apriorica

Consta in aprecierea din punct de vedere temporal a operatiilor care se utilizeaza si a costului lor relativ.

Conduce de regula la stabilirea expresiei unei functii care margineste timpul de executie al algoritmului

o      (2) Testul ulterior

Consta in stabilirea unui numar suficient de seturi de date initiale care sa acopere practic toate posibilitatile de comportament ale algoritmului

Testarea comportamentul algoritmului pentru fiecare set in parte

Se finalizeaza prin culegerea unor date in baza carora pot fi elaborate o serie de statistici referitoare la consumul de timp specific executiei algoritmului in cauza (profilul algoritmului).

• Concluzie

• Analiza apriorica are drept scop principal determinarea teoretica a ordinului de marime al timpului de executie al unui algoritm

• Testul ulterior are ca scop principal determinarea efectiva a acestui ordin prin stabilirea profilului algoritmului

3. Notatii asimptotice

• Ordinul de marime al timpului de executie al unui algoritm:

• Reprezinta o masura a eficientei algoritmului

• Permite compararea relativa a variantelor de algoritmi.

• Studiul eficientei asimptotice a unui algoritm, se realizeaza utilizand marimi de intrare cu dimensiuni suficient de mari pentru a face relevant numai ordinul de marime al timpului de executie al algoritmului.

• Intereseaza cu precadere limita la care tinde timpul de executie al algoritmului odata cu cresterea nelimitata a dimensiunii intrarii.

• De regula, un algoritm care este "asimptotic mai eficient" decat altii, va constitui cea mai buna alegere si pentru intrari de dimensiuni mici si foarte mici.

3.1. Notatia Q (teta)

• Pentru aprecierea limitei ordinului de marime al timpului de executie al unui algoritm se utilizeaza notatia Q

• Definitie. Fiind data o functie g(n), prin Q(g(n)) se desemneaza o multime de functii definita astfel:

Q(g(n)) [3.1.a]

• 
  Se spune ca o functie f(n) apartine multimii Q(g(n)), daca exista constantele pozitive c₁ si c₂  , astfel incat ea poate fi "cuprinsa" (ca un 'sandwich') intre c₁ g(n) si c₂ g(n) pentru un n suficient de mare.

Fig.3.a. Reprezentarea lui f(n) = Q(g(n))

• Desi Q(g(n)) reprezinta o multime de functii, se utilizeaza uzual notatia f(n) = Q(g(n)), cu semnificatia "f(n) este Q(g(n)) ", indicand astfel faptul ca  f(n) este membru al lui Q(g(n) sau ca f(n) I Q(g(n)) [3.1.b].

f(n) = [3.1.b]

Cu alte cuvinte pentru orice n > n₀  , f(n) este egala cu g(n) in interiorul unui factor constant.

Se spune ca g(n) este o margine asimptotica stransa ('asymptotically tight bound') a lui f(n).

Definitia lui Q necesita ca fiecare membru a lui Q(g(n)) sa fie asimptotic pozitiv, deci f(n) sa fie pozitiv pentru valori suficient de mari ale lui n.

• In practica, determinarea lui Q in cazul unei expresii, se realizeaza de regula luand in considerare termenii de ordinul cel mai mare si neglijand restul termenilor.

• Aceasta afirmatie poate fi demonstrata intuitiv, utilizand definitia formala a lui Q in a arata ca

o      Pentru aceasta, constantele c₁ , c₂ si n₀ trebuiesc determinate astfel incat, pentru orice n n sa fie valabila relatia:

.

o      Se impart membrii inegalitatii cu n² si se obtine

o      Inegalitatea din dreapta este valabila pentru orice n  1 daca il alegem pe c₂ 

o      Inegalitatea din stanga este valabila pentru orice valoare a lui n  daca se alege c₁  

o      Astfel, alegand c₁ = 1/14 , c₂ = 1/2 si n₀ = 7 se poate verifica simplu ca

Exemplul 3.1 Stabilirea functiei g(n) pentru o functie polinomiala.

Pornind de la observatia ca termenii de ordin inferior ai unei functii asimptotice pozitive pot fi neglijati

Daca se alege pentru c₁ o valoare care este cu putin inferioara coeficientului termenului celui mai semnificativ

Daca se alege pentru c₂ o valoare usor superioara aceluiasi coeficient

Inegalitatile impuse de notatia Q sunt satisfacute.

Coeficientul termenului celui mai semnificativ poate fi in continuare omis, intrucat el modifica pe c₁ si pe c₂ doar cu un factor constant egal cu coeficientul.

Fie spre exemplu functia polinomiala:

o      Neglijand termenii de ordin inferior lui 2, se ajunge la concluzia ca  f(n) = Q(n 

o      Acest lucru poate fi demonstrat si formal alegand pentru coeficienti urmatoarele valori:

, si [3.1.c]

In baza acelorasi considerente, pentru orice functie polinomiala p(n) de ordinul n unde a_i este constant si a ^d > , este valabila afirmatia p(n) = Q(n ^d) ( [3.1.d]).

Daca unde = constant si
atunci [3.1.d]

Deoarece o functie polinominala de grad zero este o constanta, despre orice functie constanta se poate spune ca este Q(n  sau Q

Desi acesta este un abuz de interpretare (deoarece n nu tinde la infinit), prin conventie Q desemneaza fie o constanta fie o functie constanta in raport cu o variabila.

3. Notatia O (O mare)

Notatia O desemneaza marginea asimptotica superioara a unei functii. Pentru o functie data g(n), se defineste O(g(n)) ca si multimea de functii:

O(g(n)) = [3.a]

Notatia O se utilizeaza pentru a desemna o margine superioara a unei functii in interiorul unui factor constant.

Pentru toate valorile n superioare lui n₀ , valoarea functiei f(n) este pe sau dedesubtul lui g(n) (fig.3.b ).

Fig.3.b. Reprezentarea lui f(n) = O(g(n))

Pentru a preciza ca o functie f(n) este membra a lui O(g(n)) se utilizeaza notatia f(n) = O(g(n)).

Faptul ca f(n) este Q(g(n)) implica ca f(n) = O(g(n)) deoarece notatia Q este mai puternica decat notatia O. Formal acest lucru se precizeaza prin relatia [3.b].

Q(g(n)) O(g(n)) [3.b]

In consecinta, deoarece s-a demonstrat faptul ca orice functie patratica a n  + b n + c , a > este Q(n  , in baza relatiei [3.b] rezulta ca aceasta functie este implicit si O(n ²).

Este surprinzator faptul ca din aceleasi considerente, functia liniara a n  + b este de asemenea O(n ²), lucru usor de verificat daca se alege c = a + | b | si n₀ = 1.

Notatia O este de obicei cea mai utilizata in aprecierea timpului de executie al algoritmilor respectiv a performantei acestora.

Ea poate fi uneori apreciata direct din inspectarea structurii algoritmului, spre exemplu existenta unei bucle duble conduce imediat la o margine de ordinul O(n ²)

Deoarece notatia O descrie o margine superioara, cand este utilizata pentru a margini cazul cel mai defavorabil de executie al unui algoritm, prin implicatie ea margineste superior comportamentul algoritmului in aceeasi masura pentru orice intrare.

In cazul notatiei Q lucrurile difera.

o      Spre exemplu, daca Q(n margineste superior cel mai defavorabil timp de executie al unui algoritm de sortare prin insertie, aceasta nu inseamna ca Q(n margineste orice intrare.

o      Astfel, daca intrarea este gata sortata, algoritmul dureaza un timp proportional cu Q(n)

Tehnic vorbind, afirmatia ca timpul de executie al unui algoritm de sortare este O(n²) constituie un abuz de limbaj.

Corect: indiferent de configuratia intrarii de dimensiune n, pentru orice valoare a lui n timpul de executie al algoritmului pentru setul corespunzator de intrari este O(n²).

Cele mai obisnuite ordine de marime ale notatiei O se afla in relatiile de ordine prezentate in [3.c], iar reprezentarea lor grafica la scara logaritmica apare in fig.3.c.

O(1) < O(log  n) < O(n) < O(n log n) < O(n ) < O(n ) <
< O(2ⁿ) < O(10 ⁿ) < O( n ! ) < O(n ⁿ)  [3.c]

Fig. 3.c. Ordine de marime ale notatiei O

In acelasi context in [3.d] se prezinta cateva sume intregi utile care sunt frecvent utilizate in calculul complexitatii algoritmilor.

[3.d]

3.3. Aritmetica ordinala a notatiei O

• In vederea aprecierii complexitatii algoritmilor in raport cu notatia O, a fost dezvoltata o aritmetica ordinala specifica care se bazeaza pe o serie de reguli formale [De89].

• Aceste reguli sunt prezentate in continuare.

• Regula 1 O(k) < O(n) pentru k .

• Regula Ignorarea constantelor: k f(n) O(f(n)) pentru k si f sau O( k f ) = O( f )

• Regula 3. Tranzitivitate: daca f(n) O(g(n)) si g(n) O(h(n)) atunci f(n) O(h(n))

Demonstratie:

f(n) = O(g(n)) T c , n f(n) c₁ g(n) pentru n > n

g(n) = O(h(n)) T c , n g(n) c₂ h(n) pentru n > n

• Se alege n₃ = max . In relatia f(n) c₁ g(n) se inlocuieste g(n) cu expresia de mai sus. Se obtine relatia:

f(n) c ( c₂ h(n))

• Alegand c₃ = c₁ c se obtine f(n) c₃ h(n) pentru n > n deci f(n) = O(h(n)).

• Regula 4 f(n) + g(n) = O( max

• Regula 5. Daca f (n) = O( g  (n)) si f  (n) = O( g  (n))
  atunci f (n) f  (n) = O( g  (n) g  (n))

• Utilizand aceste reguli se poate calcula o estimare a lui O pentru o expresie aritmetica data, fara a avea valori explicite pentru k si n.

Exemplul 3.3. Se considera expresia

8  n log(n) + 4  n

si se cere o estimare a sa in termenii notatiei O.

Se procedeaza dupa cum urmeaza:

o      log (n) = O(n^1/ 2) deoarece logaritmul unui numar este mai mic decat orice putere pozitiva a numarului in baza urmatoarei teoreme:

o      Fie a > 0 si a 

o      Pentru exponent d > 0 exista un numar  N  astfel incat pentru x > N avem log _a x < x ^d

o      n log(n) = O(n n  O(n ^3/2) (Regula 5).

o      n log(n) = O(n ^3/2) (Regula 2).

o      n  = O(n ^3/2) (Regula 2).

o      n log(n) + n  = O(max ) =

=O(max O(n ^3/2) (Regula 4).

• Rezulta in urma estimarii ca expresia 8 n log(n) + n  este O(n ^3/2).

3.4. Notatia W (Omega mare)

Notatia W (omega mare) precizeaza o margine asimptotica inferioara.

Pentru o functie data g(n), prin W(g(n)) se precizeaza multimea functiilor

= [3.4.a]

Fig. 3.d Reprezentarea lui f(n)=W(g)n))

• Teorema: Pentru oricare doua functii f(n) si g(n) , f(n) =
  daca si numai daca f(n) = O(g(n)) si f(n) = . [3.4.b]

_{Spre exemplu s-a demonstrat ca pentru orice valori ale constantelor a, b, c cu a > 0 . De aici rezulta imediat ca} .

Deoarece notatia W descrie o limita inferioara, atunci cand este utilizata
pentru a margini cazul cel mai favorabil de executie al unui algoritm, prin implicatie ea margineste inferior orice intrare arbitrara a algoritmului.

3.5. Utilizarea notatiilor asimptotice Q, O si W

Exemplul a)  Se considera formula . Cum se interpreteaza aceasta formula ?

o      In general, cand intr-o formula apare o notatie asimptotica se considera ca ea tine locul unei functii care nu se nominalizeaza explicit.

o      Astfel in exemplul de mai sus avem:

, unde .

o      Se observa faptul ca in acest caz , care este intr-adevar Q(n)

Exemplul b)  Utilizarea notatiei asimptotice poate fi de folos in eliminarea detaliilor neesentiale ale unei ecuatii.

o      Spre exemplu fie relatia recursiva:

o      Daca prezinta interes doar comportamentul asimptotic al lui T(n), nu e necesar sa fie specificati toti termenii de ordin inferior.

o      Ei sunt inclusi intr-o functie anonima, precizata prin Q(n)

Exemplul c)  Ecuatia se interpreteaza astfel: indiferent de maniera in care se alege functia anonima din partea stanga a ecuatiei, exista o modalitate de a alege functia anonima din partea dreapta, astfel incat semnul '=' sa indice o ecuatie adevarata.

o      In cazul de fata, pentru orice functie , exista _{o functie , astfel incat pentru orice n.}

o      _{De fapt} membrul drept al ecuatiei evidentiaza un grad mai redus de detaliere decat cel stang.

Exemplul d) Relatiile de acest tip pot fi inlantuite, spre exemplu:

o      Prima ecuatie precizeaza faptul ca exista o functie astfel incat pentru toti n.

o      A doua ecuatie precizeaza ca pentru orice exista o functie astfel incat pentru toti n.

o      Aceasta interpretare implica ceea ce de fapt sugereaza intuitiv lantul de egalitati.

3.6. Notatia o (o mic)

Marginea asimptotica superioara desemnata prin notatia O, poate fi din punct de vedere asimptotic stransa sau lejera (laxa).

Pentru desemnarea unei margini asimptotice lejere se utilizeaza notatia o (o mic).

= [3.6.a]

Principala diferenta dntre notatiile O si o rezida in faptul ca in cazul f(n) = O(g(n)), marginea 0 f(n) c g(n) este valabila pentru anumite constante c > , in timp ce f(n) =o(g(n)), marginea 0 g(n) < c g(n) este valabila pentru orice constanta c >

Intuitiv, in notatia o, functia f(n) devine nesemnificativa in raport cu g(n) cand n tinde la infinit [3.6.b].

f(n) = o(g(n)) implica [3.6.b]

3.7. Notatia w (omega)

Prin analogie, notatia w este pentru notatia W ceea ce este o pentru O.

Cu alte cuvinte notatia w precizeaza o margine asimptotica inferioara lejera.

= [3.7.a]

Proprietate: Relatia f(n) = w(g(n)) implica [3.7.b], adica f(n) devine in mod arbitrar semnificativa in raport cu g(n) atunci cand n tinde la infinit.

f(n) = implica [3.7.b]

3.8. Proprietati ale notatiilor asimptotice

Presupunand ca f(n) si g(n) sunt asimptotic pozitive, multe din proprietatile relationale ale numerelor reale se aplica similar comparatiilor asimptotice.

a) Tranzitivitate:

f(n) = si g(n) = implica f(n) =

f(n) = si g(n) = implica f(n) =

f(n) = si g(n) = implica f(n) =

f(n) = si g(n) = implica f(n) =

f(n) = si g(n) = implica f(n) =

b) Reflexivitate:

f(n) = ;

f(n) = ; [3.8.a]

f(n) = .

c) Simetrie:

f(n) = daca si numai daca g(n) =

d) Simetrie transpusa:

f(n) = daca si numai daca g(n) =

f(n) = o(g(n)) daca si numai daca g(n)=

Analogia dintre comparatia asimptotica a doua functii f si g si compararea a doua numere reale a si n este prezentata in 3.8.b

f(n)= a b

f(n)= a b

f(n)= a = b [3.8.b]

f(n)= a < b

f(n)= a > b

O proprietate specifica numerelor reale, care nu se aplica comparatiei asimptotice este trihotomia ('trichotomy').

o      Conform acestei proprietati intre doua numere reale oarecare exista exact una din urmatoarele relatii:

a < b ; a = b ; a > b.

o      Daca oricare doua numere reale pot fi comparate conform relatiei de mai sus, pentru doua functii f(n) si g(n) este insa posibil ca sa nu fie valabila nici f(n) = O(g(n)), nici  f(n) = W(g(n))

4. Aprecierea timpului de executie

Cu ajutorul notatiei O mare se poate aprecia timpul de executie al unui algoritm.

Se face sublinierea ca se poate aprecia timpul de executie al unui algoritm abstract si nu al unui program intrucat acesta din urma depinde de mai multi factori:

o      Dimensiunea si natura datelor de intrare,

o      Caracteristicile sistemului de calcul pe care se ruleaza programul,

o      Eficienta codului produs de compilator.

Notatia O mare permite eliminarea factorilor care nu pot fi controlati (spre exemplu viteza sistemului de calcul) concentrandu-se asupra comportarii algoritmului independent de program.

In general un algoritm a carui complexitate temporala este O(n ²) va rula ca si program in O(n ²) unitati de timp indiferent de limbajul sau sistemul de calcul utilizat.

In aprecierea timpului de executie se porneste de la ipoteza simplificatoare deja enuntata, ca fiecare instructie exceptand eventual apelurile de proceduri sau functii utilizeaza in medie aceeasi cantitate de timp.

Singurele instructiuni care nu pot fi incadrate in aceasta medie de timp sunt instructiunea IF, secventele repetitive (buclele) si apelurile de proceduri si functii.

Presupunand pentru moment ca apelurile de proceduri si functii se ignora, se adopta prin conventie urmatoarele simplificari:

• (1) Se presupune ca o instructiune IF va consuma intotdeauna timpul necesar executiei ramurii celei mai lungi, daca nu exista ratiuni contrare justificate;

• (2) Se presupune ca intotdeauna instructiunile din interiorul unei bucle se vor executa de numarul maxim de ori permis de conditia de control.

Exemplul 4.a. Se considera urmatoarea procedura care cauta intr-un tablou a cu n elemente, un element egal cu cheie si returneaza in variabila unde ultima locatie in care este gasita cheia sau zero in caz contrar [4.a].

PROCEDURE CautareLiniara(n,cheie: integer, 

a: TablouNumeric; VAR unde: integer);

VAR indice: integer;

BEGIN

unde: = 0

FOR indice:= 1 TO n DO

IF a[indice]= cheie THEN [4.a]

unde:= indice

END

Intrarea in procedura si initializarea  O(1)

variabilei unde

Bucla FOR (n reluari)  O(1+n+1) = O(n)

Instructiunea IF si O(1) O(n*1) = O(n)

ramura sa

Revenirea din procedura O(1)

Fig. 4.a. Schema temporala a algoritmului [4.a]

In figura 4.a apare schema temporala a algoritmului impreuna cu estimarea O mare corespunzatoare.

In analiza au fost introduse si operatiile de intrare si revenire din procedura care nu apar ca parti explicite ale rutinei.

Pe viitor acestea vor fi omise din analiza temporala deoarece ele contribuie cu un timp constant la executie si nu influenteaza estimarea O mare

Exemplul 4.b Se considera urmatoarea portiune de cod [4.b].

FUNCTION SumProd(n: integer): integer;

VAR rezultat,k,i: integer;

BEGIN

rezultat:= 0;

FOR k:= 1 TO n [4.b]

FOR i:= 1 TO k

rezultat:= rezultat+k*i;

SumProd:= rezultat

END;

initializare rezultat O(1)

bucla FOR (n reluari)

bucla FOR (n reluari)

O(n*1) = O(n) O(n*n) = O(n O(1+n = O(n

interior O(1)

Fig. 4.b. Schema temporala a algoritmului din secventa [4.b]

La analiza complexitatii temporale se face presupunerea ca ambele bucle se reiau de numarul maxim de ori posibil, desi acest lucru nu este adevarat deoarece bucla interioara se executa cu limita k n ( si nu cu limita n)

Se va demonstra ca prin aceasta simplificare estimarea temporala finala nu este afectata.

La o analiza mai aprofundata se tine cont de faptul ca bucla FOR interioara se executa prima oara o data, a doua oara de 2 ori s.a.m.d, a k-oara de k ori.

1 + 2 + 3 + + n = [4.c]

In mod analog in cadrul secventei [4.d] se ajunge la estimarea: O(n  n  n) = O(n³).

FOR i:= 1 TO n DO

FOR j:= 1 TO i DO

FOR k:= 1 TO i DO [4.d]

Secventa ;

• Calculul exact al numarului de reluari conduce la valoarea precizata de relatia [4.e], tinand cont de faptul ca cele doua bucle interioare se executa de i² ori la fiecare reluare a buclei exterioare FOR

1² + 2² + 3² + + n ² = = O(n ³) [4.e]

Exemplul 4.c. se refera tot la o bucla multiplicativa.

m:= 1

FOR i:= 1 TO n DO

BEGIN

m:= m *2;

FOR j:= 1 TO m DO [4.f]

Secventa

END;

In situatia in care bucla exterioara se executa pentru valorile 1, 2, 3, ale lui i, bucla interioara itereaza de 2, 4, 8, ori conducand la un timp de executie de ordinul O(2 + 4 + 8 +   + 2ⁿ).

2 + 4 + 8 + + 2ⁿ = [4.g]

Aceasta estimare este complet diferita de estimarea O(n²) pentru care exista tentatia de a fi avansata si care este valabila pentru buclele nemultiplicative.

5. Profilarea unui algoritm

Presupunand ca un algoritm a fost conceput, implementat, testat si depanat pe un sistem de calcul tinta

Ne intereseaza de regula profilul performantei sale, adica timpii precisi de executie ai algoritmului pentru diferite seturi de date, eventual pe diferite sisteme tinta.

Pentru aceasta sistemul de calcul tinta trebuie sa fie dotat cu un ceas intern si cu functii sistem de acces la acest ceas.

Dupa cum s-a mai precizat, determinarea profilului performantei face parte din testul ulterior al unui algoritm si are drept scop determinarea precisa a ordinul de marime al timpului de executie al algoritmului.

Informatiile rezultate sunt utilizate de regula pentru a valida sau invalida, respectiv pentru a nuanta rezultatele estimarii apriorice.

Se presupune un algoritm implementat in forma unui program numit Algoritm(X: Intrare,Y: Iesire)unde X este intrarea iar Y iesirea.

Pentru a construi profilul algoritmului este necesar sa fie concepute:

o      Seturile de date de intrare a caror dimensiune creste intre anumite limite, pentru a studia comportamentul algoritmului in raport cu dimensiunea intrarii

o      Seturile de date care in principiu se refera la cazurile extreme de comportament.

o      O procedura cu ajutorul careia poate fi construit profilul algoritmului in baza seturilor de date anterior amintite.

procedure Profil;

begin

*initializeaza procedura Algoritm;

*afiseaza('Testul lui Algoritm. Timpii in milisecunde');

repeat

*citeste(SetDeDate);  [5.a]

*afiseaza('Un nou set de date:', SetDeDate);

*apel TIME(t);

*apel Algoritm(SetDeDate, Rezultate);

*apel TIME(t1);

*afiseaza('TimpExecutie=', t - t1);

until sfarsit(SetDeDate)

end

Procedura Profil poate fi utilizata in mai multe scopuri functie de obiectivele urmarite.

o      (1) Evidentierea performantei intrinseci a unui algoritm precizat.

Pentru aceasta se aleg, asa cum s-a mai precizat, seturi de date cu dimensiuni din ce in ce mai mari.

Rezultatul va fi profilul algoritmului.

Pentru deplina conturare a profilului se testeaza de asemenea si cazurile de comportament extrem ale algoritmului (cel mai favorabil si cel mai defavorabil).

o      (2) Evidentierea performantei relative a doi sau mai multi algoritmi diferiti care indeplinesc aceeasi sarcina.

In acest scop se executa procedura Profil pentru fiecare din algoritmi in parte, cu aceleasi seturi de date intiale, pe un acelasi sistem de calcul.

Compararea profilelor rezultate permite ierarhizarea performantelor algoritmilor analizati.

• (3) Evidentierea performantei relative a doua sau mai multe sisteme de calcul.

• In acest scop se ruleaza procedura Profil pentru un acelasi algoritm, cu aceleasi date initiale pe sistemele de calcul tinta supuse analizei.

• Compararea profilelor rezultate permite ierarhizarea performantelor sistemelor de calcul analizate.

• De regula, pe piata sistemelor de calcul se utilizeaza in acest scop algoritmi consacrati, in anumite cazuri standardizati, cunoscuti sub denumirea de 'bench marks' in baza carora sunt evidentiate performantele diferitelor arhitecturi de sisteme de calcul.

Trebuie insa acordata o atentie speciala procedurii TIME a caror rezultate in anumite circumstante pot fi nerevelevante.

o      Astfel, in cazul sistemelor time-sharing, al sistemelor complexe (care lucreaza cu intreruperi) sau al sistemelor multi-procesor, timpul furnizat de aceasta functie poate fi complet needificator.

o      In astfel de cazuri, una din solutii este aceea de a executa programul de un numar suficient de ori si de a apela la metode statistice pentru evidentierea performantelor algoritmului testat.