Cota superior asimptòtica

En anàlisi d'algorismes una fita 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)) (o col·loquialment anomenada Notació O Gran) per referir-se a les funcions acotades superiorment per la funció g(x). Anomenada així per Edmund Landau qui va desenvolupar la teoria.

Més formalment es defineix:

$O (g (x)) = \left \{\begin{matrix}f (x): \mbox{existeixen}c, x_0> 0 \mbox{tals que}\ \\forall x \ge x_0: 0 \le|f (x)|\le 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 $x_0$, f ( x ) no sobrepassa a $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é gran importància en Teoria de la complexitat computacional a l'hora de definir les classes de complexitat.

f (x) = O (g (x)) .

Tot i que O (g (x)) està definit com un conjunt, s'acostuma 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 dóna un exemple esquemàtic de com es comporta $cg (x)$ pel que fa a f (x) quan x tendeix a infinit. Note més que aquest conjunt és no buit doncs f (x) = O (g (x)) .

La cota ajustada asimptòtica (notació Θ) té relació amb les cotes asimptòtiques superior i inferior (notació Ω):

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

Propietats

Sigui $I \subseteq \mathbb{R}$, siguin $f_1: I \to \mathbb{R}$, $g_1: I \to \mathbb{R}$, $F_2: I \to \mathbb{R}$, $g_2: I \to \mathbb{R}$ funcions i $k$ un real. Llavors els següents enunciats són certs

I) Si $f_1 = O (g_1) \,$ i $g_1 = O (g_2) \,$, aleshores $f_1 = O (g_2) \,$

Ii) Si $f_1 = O (g_1) \,$ i $F_2 = O (g_2) \,$, aleshores $f_1f_2 = O (g_1g_2) \,$

Iii) $f_2O (g_1) = O (f_2g_1) \,$ (aquí és igualtat entre conjunts)

Iv) Si $f_1 = O (g_1) \,$ i $F_2 = O (g_2) \,$, aleshores $f_1+F_2 = O (|g_1|+|g_2|) \,$

V) Si $k \neq 0 \,$ llavors $O (g_1) = O (kg_1) \,$ (aquí és igualtat entre conjunts)

Vi) Si $f_1 = O (g_1) \,$, aleshores $kf_1 = O (g_1) \,$.

Exemples

• La funció x+10 pot ser fitada superiorment per la funció 11x ² . Per demostrar prou notar que per a tot valor de x ≥ 1 es compleix x+10 ≤ 11x ² . Per tant x+10 = O (x ²) . No obstant això, x ² no serveix com a cota inferior per x+10 , és a dir, $11x^2$ ≠ $O (x+10)$.
  Observació: Aquest exemple mostra que l'ús del símbol "=" està mal emprat (matemàticament) ja que la notació de Landau (O gran) no és reflexiva.
• La funció x ²+200x està fitada superiorment per x ² . Vol dir que quan x tendeix a infinit el valor de 200x es pot menysprear pel que fa al 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 subalgorítmic
O (log n )	Ordre logarítmic
O ($\sqrt n$)	Ordre sublineal
O ( n )	Ordre lineal
O ( n · log n )	Ordre lineal logarítmic
O ( n c )	Ordre potencial
O ( c n ), n> 1	Ordre exponencial
O ( n ! )	Ordre factorial

Vegeu també

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

Bibliografia

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