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.

f(x) funtzio bat O(g(x))-rena da, c konstante positibo bat dagoenean, non  baliotik aurrera f(x) ez baita hau baino handiagoa izango:  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. 

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 

Kategoria:Informatika
Kategoria:Matematika