Cota superior asimptòtica

Plantilla:Millorar traducció 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:

$O(g(x))=\left\{\begin{array}{c}f(x):\text{existeixen }{x}_0,c>0\text{ tals que}\\ \mathrm{\forall }x\ge x_0>0:0\le |f(x)|\le c|g(x)|\end{array}\right\}$

Una funció f(x) pertany a O(g(x)) quan hi ha una constant positiva c tal que a partir d'un valor $x_0$, $f(x)$ 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 $cg(x)$ 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:

$f(x)=\mathrm{\Theta }(g(x))\text{ si i només si }f(x)=O(g(x))\text{ i }f(x)=\mathrm{\Omega }(g(x))$

Propietats

Sigui $E\subseteq ℝ$, siguin $f_1:E\to ℝ$, $g_1:E\to ℝ$, $f_2:E\to ℝ$, $g_2:E\to ℝ$ funcions i $k$ un real. És compleixen els següents enunciats:

i) Si $f_1=O(g_1)$ y $g_1=O(g_2)$, llavors $f_1=O(g_2)$

ii) Si $f_1=O(g_1)$ y $f_2=O(g_2)$, llavors $f_1{f}_2=O(g_1{g}_2)$

iii) $f_{2}O(g_1)=O(f_2{g}_1)$ (igualtat entre conjunts)

iv) Si $f_1=O(g_1)$ y $f_2=O(g_2)$, llavors $f_1+f_2=O(|g_1|+|g_2|)$

v) Si $k\ne 0$ llavors $O(g_1)=O(k{g}_1)$ (igualtat entre conjunts)

vi) Si $f_1=O(g_1)$, llavors $k{f}_1=O(g_1)$.

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 $x^2\ne ◯(x+10)$.
• 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ó	nom
O(1)	ordre constant
O(log log n)	ordre sublogarítmic
O(log n)	ordre logarítmic
O($\sqrt{n}$)	ordre sublineal
O(n)	ordre lineal o de primer ordre
O(n · log n)	ordre lineal logarítmic
O(n²)	ordre quadràtic o de segon ordre
O(n3), ...	ordre cúbic o de tercer ordre, ...
O(nc)	ordre potencial fix
O(cn), n > 1	ordre exponencial
O(n!)	ordre factorial
O(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