Granda O

En matematiko, **granda O** estas la simbolo *O* uzata por priskribi asimptotan superan baron por la grandeco de funkcio per alia, kutime pli simpla, funkcio.

Estas ankaŭ la aliaj simboloj *o, Ω, ω, Θ, Õ* por diversaj aliaj superaj, subaj kaj striktaj baroj (vidu sube).

## Difino 
Estu *f(x)* kaj *g(x)* estas du funkcioj sur iu subaro de la reelaj nombroj. Tiam *f(x)* estas de la ordo de *g(x)* kiam *x* proksimiĝas al plus malfinio (kio estas f(x) \in \mathcal{O}(g(x))) se kaj nur se ekzistas pozitiva reela nombro *c* kaj reela nombro *x0* tiaj ke *|f(x)| x0*.

Per formuloj ĉi tio estas:

:f(x) \in \mathcal{O}(g(x))\mbox{ kun }x\to+\infty

se kaj nur se

:\exists \;x_0,\exists \;c>0\mbox{ tia ke } |f(x)| \leqslant \; c |g(x)|\mbox{ por }x>x_0.

Tia notacio povas esti uzita ankaŭ por priskribi konduton de *f(x)* proksime al iu reela nombro *a*:

:f(x) \in \mathcal{O}(g(x))\mbox{ kun }x\to a

se kaj nur se

:\exists \;\delta >0,\exists \; c>0\mbox{ tia ke }|f(x)| \leqslant \; c |g(x)|\mbox{ por }|x - a| 

Se *g(x)* estas ne-nula por valoroj de *x* sufiĉe proksime al *a*, ambaŭ ĉi tiuj difinoj povas esti unuece skribitaj per la limigo supera:

:f(x)) \in \mathcal{O}(g(x))\mbox{ kiam }x \to a

se kaj nur se

:\limsup_{x\to a} \left|\frac{f(x)}{g(x)}\right| 

## Uzado 
La notacio kun granda O estas utila en analizo de rula tempo de algoritmoj.

En matematiko, ambaŭ asimptotaj kondutoj proksime al ∞ kaj proksime al iu *a* estas uzatadaj. En komputa komplikteorio, nur asimptotoj proksime al ∞ estas uzataj kun nur pozitivaj funkcioj estas konsiderata, tiel la esprimo de absoluta valoro povas esti ellasita el la formuloj de la difino.

## Ekzemploj 
### Malfinia asimptoto 
Ekzemple, la tempo (aŭ la kvanto de ŝtupoj) bezonata por plenumi problemon de amplekso *n* estu *T(n) = n2 - n + 2*.

Se *n* kreskas kaj iĝas grandan, la termo *n2*, estos ĉiam domina, tiel ke ĉiuj alia termoj povas esti neglektitaj. Ekzemple por *n=1000*, la termo *n2* estas je 1000 fojoj pli granda ol la termo *n*. Ignoro de la lasta devas ne havi konsiderindan efikon por plejparto de pritaksoj de rula tempo.

:T(n)\in \mathcal{O}(n^2)

Plu, la koeficientoj iĝas negravajn se oni komparas la ordojn. Ekzemple estu termoj *n2* kaj *n3*. Eĉ se *S(n)=n2* kaj *U(n)=0,01n3*, la lasta estas pli granda ol la unua por *n>100*. Por plu pli grandaj *n*, ekzemple *n=109*, diferenco inter *S(n)* kaj *U(n)* estas multe pli granda ol inter *U(n)* kaj *V(n)=n3*: *S(109)=1018, U(109)=1025, V(109)=1027*.

Tiel la granda *O* kaptas tion kio restas:

:S(n)\in \mathcal{O}(n^2)
:U(n)\in \mathcal{O}(n^3)
:V(n)\in \mathcal{O}(n^3)

### Finia asimptoto 
Granda *O* povas ankaŭ esti uzata por priskribi la eraran termon en proksimuma kalkulado de funkcio. Ekzemple,

:e^x=1+x+\frac{x^2}{2}+\mathcal{O}(x^3)\quad\hbox{kiam}\ x\to 0

esprimas la fakton ke la eraro, la diferenco e^x - \left(1 + x +\frac{x^2}{2}\right), estas pli malgranda en absoluta valoro ol iu konstanto multiplikita per \left|x^3\right| kiam *x* proksimiĝas al 0.

## Problemoj pri la notacio 
*O(f(x))* signifas kolekton de funkcioj *g(x)* de variablo *x*, tiaj ke ilia kreskado estas limigita per kreskado de *f(x)* en iu respekto. La tradicia notacio por tio ke *g(x)* apartenas al ĉi tiu kolekto estas:

: *g(x) = O(f(x))*

Ĉi tiu uzo de la egala signo estas nerigora notacio, pro tio ke la pli supra frazo ne estas ekvacio. Estas malvere konkludi de *g(x) = O(f(x))* kaj *h(x) = O(f(x))* ke *g(x)=h(x)*. Unu el variantoj estas opinii ke ĉi tie "= *O*" estas unu simbolo. Al eviti la problemon, iuj aŭtoroj preferas skribi anstataŭe kiel:

:g(x) \in \mathcal{O}(f(x))

sen diferenco en signifo. Noto ankaŭ, ke ĉi tie en notacio kun simbolo "=" ne eblas interŝanĝi la flankojn, oni ne skribas kiel

: *O(f(x)) = g(x)*

La komunaj aritmetikaj operacioj estas ofte etenditaj al la klasa koncepto. Ekzemple, *h(x) + O(f(x))* signifas kolekton de funkcioj havantaj la kreskadon de *h(x)* plus parto kies kreskado estas limigita al tiu de *f(x)*. Tial,

:g(x) = h(x) + \mathcal{O}(f(x))

estas la samo kiel

:g(x) - h(x) \in \mathcal{O}(f(x))

Alia anomalio de la notacio, kvankam malpli escepta, estas ke oni ne eksplicitas kiu variablo estas la funkcia argumento, kaj ĉi tion bezonatas konkludi de la ĉirkaŭteksto se kelkaj variabloj estas koncernataj. En la ekzemplo du dekstraj flankoj uzantaj la notacion de granda O havas ege malsamajn signifojn:

:f(m) = \mathcal{O}(m^n)
:g(n) = \mathcal{O}(m^n)

En la unua okazo *f(m) havas polinoman kreskadon, en la dua por *m>1*, *g(n)* havas eksponentan kreskadon.

Fina anomalio estas ke la notacio ne montras klare kie la funkcia kreskado estas konsiderata; proksime al iu punkto aŭ al la malfinio. Ĉi tiu estas en kontrasto kun la kutima notacio por limigoj.

En pli kompleksa uzado, O( ) povas aperi en malsamaj lokoj en ekvacio, eĉ kelkfoje en ĉiu flanko. Ekzemple, jeno estas vera por n\to\infty

:(n+1)^2 = n^2 + \mathcal{O}(n)
:(n+\mathcal{O}(n^{1/2}))(n + \mathcal{O}(\log\,n))^2 = n^3 + \mathcal{O}(n^{5/2})
:n^{\mathcal{O}(1)} = \mathcal{O}(e^n)

La signifo de la propozicioj estas: por *ĉiuj* funkcioj kiu kontentigas ĉiun O( ) maldekstre, estas *iuj* funkcioj kontentigantaj ĉiun O( ) dekstre, tiaj ke enmeto de ĉi ĉiuj funkcioj en la ekvacion faras la du flankojn egalajn. Ekzemple, la tria ekvacio pli supre signifas ke por ĉiu funkcio *f(n)=O(1)*, estas iu funkcio *g(n)=O(en)* tia ke *nf(n)=g(n)*. En terminoj de la ara notacio kiel pli supre, la signifo estas ke la klaso de funkcioj prezentitaj per la maldekstra flanko estas subaro de la klaso de funkcioj prezentitaj per la dekstra flanko.

Estas ankaŭ problemo ke la simbolo *f(x)* signifas la valoron de la funkcio *f* por la argumento *x*, sed ne la funkcion entute. La simbolo de la funkcio estas *f* sed ne *f(x)*. Por ĉi tio, iuj aŭtoroj preferas skribi kiel

: f \in \mathcal{O}(g).

## Ecoj 
Jen estas listo de klasoj de funkcioj kiuj estas kutime estadas en analizo de algoritmoj. Ĉi tie *n* pligrandiĝas al malfinio. La pli malrapide kreskantaj funkcioj estas listitigiaj komence. *c* estas ajna konstanto.

Se funkcio *f(n)* povas esti skribita kiel finia sumo de aliaj funkcioj, tiam la plej rapide kreskanta ero difinas la ordon de *f(n)*. Ekzemple
:f(n) = 3 \log n + 7 (\log n)^3 + 4n^2 + 5n^3 \in \mathcal{O}(n^3)\,\!.

Aparte, se funkcio povas esti barita per polinomo en *n*, tiam kiel *n* strebas al malfinio, oni povas malobservi termoj de ne la plej granda ordo de la polinomo.

Por *c>1*, *O(nc)* kaj *O(cn)* estas tre malsamaj. La lasta kreskas multe, multe pli rapida, sendepende de la konstanto *c* estas (se ĝi estas pli granda ol unu). Funkcio kiu kreskas pli rapida ol ĉiu potenco de *n* estas *superpolinoma*. Funkcio kiu kreskas pli malrapide ol ĉiu eksponenta funkcio de formo c^n estas *subeksponenta*. Funkcio povas esti ambaŭ superpolinoma kaj subeksponenta. Ekzemple ĉi tia estas tempo de ĝenerala nombra kampa kribrilo, la plej rapida sciata algoritmo por entjera faktorigo, kiu por *b*-bita nombro estas:

:O\left(\exp\left(\left(\frac{64b}{9}\right)^{1\over3} (\log b)^{2\over3}\right)\right).

*O(log(nc))* estas akurate la samo kiel *O(log n)*. La logaritmoj diferenciĝas nur per konstanta faktoro pro tio ke *log(nc)=c log n* kaj tial la granda *O* ignoras la diferencon. Simile logaritmoj kun malsamaj konstantaj bazoj estas ekvivalentaj. Eksponentoj kun malsamaj bazoj, male, estas ne de la sama ordo. Ekzemple, *2n* kaj *3n* estas ne de la sama ordo.

Por ĉiu *k>0* kaj ĉiu *c>1*, *O(nc log(nk))* estas subaro de *O(log(n(c+a)))* por ĉiu *a>0*. Tiel ofte estanta kresko *O(nc log(nk))* povas esti konsiderata kiel polinoma kun malmulte pli granda potenco.

Multipliko de la variablo per konstanto povas afekti aŭ ne afekti la ordon de la kresko. Ekzemple, se la ordo estas *n2*, anstataŭigo de *n* per *cn* signifas ordon de *c2n2*, kaj la granda O ignoras la konstanton *c2*. Ĉi tio povas esti skribita kiel c^2n^2 \in \mathcal{O}(n^2) . Tamen se la ordo estas *2n*, anstataŭigo de *n* per *cn* donas ordon 2^{cn} = (2^c)^n, kiu ne estas ekvivalento al *2n* (se *c≠1*).

Ŝanĝo de la variablo povas ŝanĝi la formulon por ordo de kresko, ne ŝanĝante la realan tempon de ruligo. Ekzemple, por primeco-testo AKS, la tempo estas *O((log n)c)* se *n* estas la kontrolata nombro kaj *O(nc)* se *n* estas kvanto de ciferoj en la nombro.

Eblas pli granda kreskado ol komune estantaj, ekzemple la solo-valora versio de la akermana funkcio, *A(n,n)*. Male, estadas ege malrapide kreskantaj funkcioj, ekzemple la inverso de ĉi tiu funkcio *A(n,n)*, ofte skribata kiel *α(n)*. Kvankam *α(n)* estas nebarita (proksimiĝas al malfinio kiam *n* proksimiĝas al malfinio), ĉi tiaj funkcioj estas ofte proksimumataj kiel konstantaj faktoroj por ĉiuj praktikaj celoj.

### Produto 
: f_1 \in\mathcal{O}(g_1)\ \wedge\ f_2\in\mathcal{O}(g_2)\, \implies f_1 f_2\in\mathcal{O}(g_1 g_2)\,

:f\cdot \mathcal{O}(g) \in \mathcal{O}(f g)

### Sumo 
: f_1 \in\mathcal{O}(g_1)\ \wedge\ f_2\in\mathcal{O}(g_2)\, \implies f_1 + f_2\in\mathcal{O}(g_1 + g_2)\,
::Ĉi tiu implicas f_1 \in \mathcal{O}(g) \land f_2 \in \mathcal{O}(g) \implies f_1+f_2 \in \mathcal{O}(g) , kio signifas ke O(g) estas konveksa konuso.

:f + \mathcal{O}(g) \in \mathcal{O}(f + g)

### Multipliko per konstanto 
Por  k \in \R_{>0} .

:\mathcal{O}(k \cdot g) = \mathcal{O}(g)

:f\in \mathcal{O}(g) \Rightarrow k\cdot f\in \mathcal{O}(g) 

## Rilatantaj asimptotaj rilatoj 
### Malgranda o 
La rilato f(x) \in o(g(x)) signifas ke *f(x)* kreskas multe pli malrapide ol *g(x)*, do la limigo de *f(x)/g(x)* estas nulo, kiam *x* proksimiĝas al malfinio aŭ al certa valoro.

Ekzemple por x\to\infty:

* 2x \in o(x^2) \,\!
* 2x^2 \not \in o(x^2)
* 1/x \in o(1)

Jenaj ecoj validas:

* o(f) + o(f) \subseteq o(f)
* o(f)o(g) \subseteq o(fg)
* o(o(f)) \subseteq o(f)
* o(f) \subset O(f), kaj tial la ecoj de *O* aplikeblas al kombinaĵoj de *o* kaj *O*.

Simile al granda *O*, la frazo "*f(x)* estas *o(g(x))*" estas kutime skribata kiel *f(x) = o(g(x))*, kio estas nerigora notacio.

### Aliaj 
\log^kn estas ĉiam o(n^a) por ĉiu konstanto *k* kaj ĉiu konstanto *a>0*.

La L-notacio, difinita kiel

:L_n[\alpha, c] = O\left(e^{((c + o(1))(\ln n)^\alpha(\ln\ln n)^{1-\alpha})}\right),

estas oportuna por funkcioj kiuj estas inter polinomo kaj eksponenta funkcio.

## Multaj variabloj 
Granda O kaj malgranda o, kaj la aliaj povas ankaŭ esti uzataj kun multaj variabloj. Ekzemple, la frazo

:f(n,m) = n^2 + m^3 + \hbox{O}(n+m) \mbox{ kun } n,m\to\infty

asertas ke ekzistas konstantoj *C* kaj *N* tiaj ke

:\forall n, m>N: |f(n,m) - (n^2 + m^3)| \le C(n+m).

Por konkreteco la ŝanĝiĝanta variablo devus ĉiam esti precizigita: la frazo

:f(n,m) = \hbox{O}(n^m) \mbox{ kun } n,m\to\infty

estas sufiĉe malsama ol

:\forall m: f(n,m) = \hbox{O}(n^m) \mbox{ kun } n\to\infty.

## Vidu ankaŭ 
* Rapida ordigo

## Referencoj 
## Eksteraj ligiloj 
* Enkonduko al asimptotaj notacioj 
* Vikilibroj pri granda *O*
* Donald Knuth. *Granda Omicron kaj granda Omego kaj granda Θ'', ACM SIGACT Novaĵoj, Volumeno 8, Eldono 2, 1976.
* Formaligo de O-notacio
* Granda O-notacio
* Notacio kun malgranda o
* "Ω"
* "ω"
* "Θ"

Kategorio:Matematika notacio
Kategorio:Asimptota analitiko