Vés al contingut

Anàlisi asimptòtica

De la Viquipèdia, l'enciclopèdia lliure

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ó

[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 prou grossos). 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 externes

[modifica]