Vés al contingut

Usuari:Mcapdevila/Cota superior asimptòtica

De la Viquipèdia, l'enciclopèdia lliure

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 es fa servir 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:

Una funció f ( x ) pertany a O ( g ( x )) quan hi ha una constant positiva c tal que a partir d'un valor , f ( x ) no sobrepassa a . 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 a escriure f (x) = O (g (x)) en comptes de f (x) ∈ O (g (x)). Moltes vegades també es parla d'una funció nomenant únicament la seva expressió, com en x ² en comptes 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 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ó Ω):

Propietats

[modifica]

Sigui , siguin , , , funcions i un real. Llavors els següents enunciats són certs

I) Si i , aleshores
Ii) Si i , aleshores
Iii) (aquí és igualtat entre conjunts)
Iv) Si i , aleshores
V) Si llavors (aquí és igualtat entre conjunts)
Vi) Si , aleshores .

Exemples

[modifica]
  • 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, .
    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]

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 () Ordre sublineal
O ( n ) Ordre lineal
O ( n · log n ) Ordre lineal logarítmic
O ( n c ) Ordre polinòmic o potencial
O ( c n ), n> 1 Ordre exponencial
O ( n ! ) Ordre factorial

Vegeu també

[modifica]

Bibliografia

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