Anàlisi asimptòtica

En els camps de les matemàtiques pures i aplicades, en particular en l'anàlisi d'algorismes, l'anàlisi asimptòtica és un mètode de descripció del comportament en el límit quan una o més variables tendeixen cap a infinit.

Per exemple, suposem que estem interessats en les propietats d'una funció f(n) quan n es fa molt gran. Si f(n) = n2 + 3n, aleshores quan n es fa molt gran, el terme 3n esdevé insignificant comparat amb n2. La funció f(n) es diu que és "asimptòticament equivalent a n2, quan n → ∞". Això s'escriu habitualment amb la notació f(n) ~ n2, i es llegeix com que "f(n) és asimptòtica a n2".

DefinicióModifica

Formalment, donades dues funcions f(x) i g(x), definim una relació binària

 

si i només si (de Bruijn 1981, §1.4)

 

Això defineix una relació d'equivalència (en el conjunt de funcions diferents de zero per a tots els valors de x suficientment grans). La majoria de matemàtics prefereix la definició

 

seguint la notació de Landau, que evita aquesta limitació. La classe d'equivalència de f consta de totes les funcions g que "es comporten com" f en el límit.

Vegeu tambéModifica

Referències externesModifica