Goi borne asintotiko

Wikipedia, Entziklopedia askea
Jump to navigation Jump to search

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.

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.

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

Bibliografia[aldatu | aldatu iturburu kodea]

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

Ikus, gainera[aldatu | aldatu iturburu kodea]

Kanpo estekak[aldatu | aldatu iturburu kodea]