Anàlisi asimptòtica

Aquest article o secció no cita les fonts o necessita més referències per a la seva verificabilitat.

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 ) ∼ g ( x ) ( quan  x → ∞ ) {\displaystyle f(x)\sim g(x)\quad ({\text{quan }}x\to \infty )}

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

lim x → ∞ f ( x ) g ( x ) = 1. {\displaystyle \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 prou grossos). La majoria de matemàtics prefereix la definició

f ∼ g ⟺ f − g = o ( g ) {\displaystyle 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é

Referències externes

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