Cota superior asimptòtica

De Viquipèdia
Dreceres ràpides: navegació, cerca

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): \exists c,\ \exists x_0> 0\ \ \mbox{tals que,}\ \forall x \ge x_0\ \mbox{es compleix}\ 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[modifica | modifica el codi]

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[modifica | modifica el codi]

  • 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[modifica | modifica el codi]

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é[modifica | modifica el codi]

Bibliografia[modifica | modifica el codi]

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