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) = n² + 3n, aleshores quan n es fa molt gran, el terme 3n esdevé insignificant comparat amb n². La funció f(n) es diu que és "asimptòticament equivalent a n², quan n → ∞". Això s'escriu habitualment amb la notació f(n) ~ n², i es llegeix com que "f(n) és asimptòtica a n²".

Definició

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

$f(x)\sim g(x)\quad ({\text{quan }}x\to \infty )$

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

$\lim _{x\to \infty }{\frac {f(x)}{g(x)}}=1.$

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ó

$f\sim g\iff f-g=o(g)$

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é

• Asímptota
• Notació de Landau

Referències externes

• Weisstein, Eric W., «Asymptotic Analysis» a MathWorld (en anglès).
• Weisstein, Eric W., «Asymptotic Notation» a MathWorld (en anglès).