Analiza algoritmului asimptotic

44


    În Secţiunea urmatoare vom vedea un algoritm mai inteligent care durează un timp proporţional cu n2. Este aproape evident că un algoritm care necesită un timp proporţional cu n2 este mult mai eficient decât unul a cărui durată este proporţională cu 22n.

    Pentru a formaliza această observaţie, vom introduce notaţia “O mare” (O(x) este folosit în matematică pentru a estima ordinul de mărime, gradul unei expresii, etc.).

Definiţie: Fie două funcţii f(n) şi g(n). Atunci f(n)=O(g(n)) dacă şi numai dacă există o constantă c astfel încât, pentru n suficient de mare, |f(n)|≤c.g(n)

    De exemplu 100n2+100n şi 1000n2+120n+1000 sunt amândouă O(n2).

© Cornel Mironel Niculae, 2003-2008

13-Nov-2009