Cota superior asimptòtica

Aquest article o secció necessita millorar una traducció deficient. Podeu col·laborar-hi si coneixeu prou la llengua d'origen. També podeu iniciar un fil de discussió per consultar com es pot millorar. Elimineu aquest avís si creieu que està solucionat raonablement.

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:

${\displaystyle O(g(x))=\left\{{\begin{matrix}f(x):{\mbox{existeixen }}x_{0},c>0{\mbox{ tals que}}\\\forall x\geq x_{0}>0:0\leq |f(x)|\leq c|g(x)|\end{matrix}}\right\}}$

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

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

Sigui ${\displaystyle E\subseteq \mathbb {R} }$, siguin ${\displaystyle f_{1}:E\to \mathbb {R} }$, ${\displaystyle g_{1}:E\to \mathbb {R} }$, ${\displaystyle f_{2}:E\to \mathbb {R} }$, ${\displaystyle g_{2}:E\to \mathbb {R} }$ funcions i ${\displaystyle k}$ un real. És compleixen els següents enunciats:

i) Si ${\displaystyle f_{1}=O(g_{1})\,}$ y ${\displaystyle g_{1}=O(g_{2})\,}$, llavors ${\displaystyle f_{1}=O(g_{2})\,}$

ii) Si ${\displaystyle f_{1}=O(g_{1})\,}$ y ${\displaystyle f_{2}=O(g_{2})\,}$, llavors ${\displaystyle f_{1}f_{2}=O(g_{1}g_{2})\,}$

iii) ${\displaystyle f_{2}O(g_{1})=O(f_{2}g_{1})\,}$ (igualtat entre conjunts)

iv) Si ${\displaystyle f_{1}=O(g_{1})\,}$ y ${\displaystyle f_{2}=O(g_{2})\,}$, llavors ${\displaystyle f_{1}+f_{2}=O(|g_{1}|+|g_{2}|)\,}$

v) Si ${\displaystyle k\neq 0\,}$ llavors ${\displaystyle O(g_{1})=O(kg_{1})\,}$ (igualtat entre conjunts)

vi) Si ${\displaystyle f_{1}=O(g_{1})\,}$, llavors ${\displaystyle kf_{1}=O(g_{1})\,}$.

• 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 ${\displaystyle x^{2}\neq \bigcirc (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².

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(${\displaystyle {\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

• Cota inferior asimptòtica
• Cota superior asimptòtica
• Notació de Landau

• Introduction to Algorithms, Second Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein