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:
Una funció f(x) pertany a Ω(g(x)) quan hi ha una constant positiva c tal que a partir d'un valor , 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 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:
This article uses material from the Wikipedia Català article Cota inferior asimptòtica, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). El contingut està disponible sota la llicència CC BY-SA 4.0 si no s'indica el contrari. Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki Català (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.