Aprecierea timpului de executie

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.