En anàlisi d'algorismes una cota superior asimptòtica és una funció que serveix de cota superior d'una altra funció quan l'argument tendeix a infinit. Usualment s'utilitza la notació de Landau: O(g(x)), per referir-se a les funcions acotades superiorment per la funció g(x). Més formalment es defineix:
Una funció f(x) pertany a O(g(x)) quan hi ha una constant positiva c tal que a partir d'un valor , no supera cg(x). Vol dir que la funció f és inferior a g a partir d'un valor donat excepte per un factor constant.
La cota superior asimptòtica té utilitat en Teoria de la complexitat computacional quan es defininen les classes de complexitat.
Tot i que O(g(x)) està definit com un conjunt, s'acostuma a escriure f(x)= O(g(x)) en lloc de f(x)∈ O(g(x)). Moltes vegades també es parla d'una funció nomenant únicament la seva expressió, com en x² en lloc de h(x)=x², sempre que estigui clar quin és el paràmetre de la funció dins de l'expressió. En la gràfica es dona un exemple esquemàtic de com es comporta pel que fa a f(x) quan x tendeix a infinit. Cal notar a més que aquest conjunt és no buit doncs g(x)=O(g(x)).
La cota ajustada asimptòtica (notació Θ) té relació amb les cotes asimptòtiques superior (notació O) i inferior:
Propietats Sigui , siguin , , , funcions i un real. És compleixen els següents enunciats:
i) Si y , llavors
ii) Si y , llavors iii) (igualtat entre conjunts) iv) Si y , llavors v) Si llavors (igualtat entre conjunts) vi) Si , llavors .
Exemples La funció f(x) = x + 10 pot ser fitada superiorment per la funció g(x) = x². Per demostrar-ho és prou notar que per a tot valor de x≥3.7016 es compleix x+10 ≤ x². Per tant, x+10 = O(x²). Però x² no serveix com a cota inferior per x+10, és a dir . La funció 200x està fitada superiorment per x². Vol dir que quan x tendeix a infinit el valor de 200x es pot menysprear comparat amb el de x².
Ordres usuals per a funcions Els ordres més utilitzats en anàlisi d'algorismes, en ordre creixent, són els següents (on c representa una constant i n la mida de l'entrada): notació nomO(1)ordre constantO(log log n)ordre sublogarítmicO(log n)ordre logarítmicO()ordre sublinealO(n)ordre lineal o de primer ordreO(n · log n)ordre lineal logarítmicO(n²)ordre quadràtic o de segon ordreO(n3), ...ordre cúbic o de tercer ordre, ...O(nc)ordre potencial fixO(cn), n > 1ordre exponencialO(n!)ordre factorialO(nn)ordre potencial exponencial
Vegeu també Cota inferior asimptòtica Cota superior asimptòtica Notació de Landau
Bibliografia Introduction to Algorithms, Second Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
Categoria:Anàlisi matemàtica