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.

$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 $x_{0}$ baliotik aurrera f(x) ez baita hau baino handiagoa izango: $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.

f (x) = O (g (x)) .

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. $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