Cota ajustada asimptòtica

En anàlisi d'algorismes, una cota ajustada asimptòtica és una funció que serveix de cota tant superior com inferior d'una altra funció quan l'argument tendeix a infinit. Usualment s'utilitza la notació Θ g(x) per referir-se a les funcions acotades per la funció g(x).

Més formalment es defineix:

f(x)(g(x))

Una funció f(x) pertany a Θg(x) quan existeixen constants positives i tals que a partir d'un valor f(x) es troba atrapada entre i . Vol dir que les funcions f i g són iguals a partir d'un valor donat llevat per una factor constant. Per tant té sentit prendre a g com un representant de f.

Tot i que Θ g(x) està definit com un conjunt, s'acostuma a escriure f(x)=Θ(g(x)) en lloc de f(x)∈Θg(x). Moltes vegades també es parla de la funció 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 comporten i pel que fa a f(x) quan x tendeix a infinit.

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

Exemples

modifica
  • La funció f(x)= x+10 pot ser fitada per la funció g(x)=x. Per demostrar prou notar que per a tot valor de x≥1 es compleix que g(x)≤f(x)≤11g(x), és a dir xx+10≤11x. Per tant x+10=Θ(x).

Vegeu també

modifica

Bibliografia

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