Goi borne asintotiko

Analisi algoritmikoan, goi-borne asintotiko bat beste funtzio baten goi-borne gisa erabiltzen den funtzio bat da, argumentuak infiniturantz jotzen duenean. Normalean, Landauren notazioa erabiltzen da: O(g(x)), g(x)-ren agindua, hizkera arruntean Notazio O Handia deiturikoa, g(x) funtzioak gainetik mugatutako funtzioei erreferentzia egiteko.

${\displaystyle O(g(x))=\left\{{\begin{matrix}f(x):{\mbox{existitzen da }}x_{0},c>0{\mbox{ non}}\\\forall x\geq x_{0}>0:0\leq |f(x)|\leq c|g(x)|\end{matrix}}\right\}}$

f(x) funtzio bat O(g(x))-rena da, c konstante positibo bat dagoenean, non ${\displaystyle x_{0}}$ baliotik aurrera f(x) ez baita hau baino handiagoa izango: ${\displaystyle cg(x)}$ Horrek esan nahi du f funtzioa g baino txikiagoa dela emandako balio batetik abiatuta, faktore konstante batek izan ezik.

Goi borne asintotikoak berebiziko garrantzia du Konplexutasun Konputazionalen Teorian konplexutasun klaseak zehazterakoan.

Nahiz eta O(g(x)) multzo gisa definituta egon, f(x)=O(g(x))) idatzi ohi da f(x) O(g(x)-ren ordez. Askotan, funtzioaz hitz egiten da soilik bere adierazpena izendatuz, h(x)=x² -ren ordez, baldin eta argi badago zein den funtzioaren parametroa adierazpenaren barruan. Grafikoan, portaera horren adibide eskematikoa ematen da. ${\displaystyle cg(x)}$

f(x)-rekiko, x infiniturantz jotzen duenean. Gainera, multzo hori ez da hutsa, g(x)=O(g(x)) baita.

Bibliografia

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

Ikus, gainera

• Ordenatze algoritmo
• Funtzio
• Matematika

Kanpo estekak

• Datuak: Q269878