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, 200
3-200813-Nov-2009