Cota inferior asimptòtica

f(x)=Ω(g(x))

En anàlisi d'algorismes una cota inferior asimptòtica és una funció que serveix de cota 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 inferiorment per la funció g(x). Més formalment es defineix:

Ω ( g ( x ) ) = { f ( x ) : existeixen  c , x 0  constants positives tals que ∀ x : x 0 ≤ x : 0 ≤ c g ( x ) ≤ f ( x ) } {\displaystyle \Omega (g(x))=\left\{{\begin{matrix}f(x):{\mbox{existeixen }}c,x_{0}{\mbox{ constants positives tals que}}\\\forall x:x_{0}\leq x:0\leq cg(x)\leq f(x)\end{matrix}}\right\}}

Una funció f(x) pertany a Ω(g(x)) quan hi ha una constant positiva c tal que a partir d'un valor x 0 {\displaystyle x_{0}} , c g ( x ) {\displaystyle cg(x)} no supera f(x). Vol dir que la funció f és superior a g a partir d'un valor donat excepte per un factor constant.

La cota inferior asimptòtica té utilitat en teoria de la complexitat computacional a l'hora de calcular la complexitat del millor cas per als algorismes.

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 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 c g ( x ) {\displaystyle cg(x)} pel que fa a f(x) quan x tendeix a infinit.

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

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

Exemples

  • La funció x² pot ser fitada inferiorment per la funció x. Per demostrar prou notar que per a tot valor de x≥1 es compleix x≤x². Per tant x²=Ω(x) (però x no serveix com a cota superior per x²).
  • La funció x²+200x està fitada inferiorment per x². Vol dir que quan x tendeix a infinit el valor de 200x es pot menysprear pel que fa al de x².

Vegeu també

Bibliografia

  • Introduction to Algorithms, 2a ed. per Thomas H. Corman, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (anglès)